#include <assert.h>
#include<stdio.h>
#include <vector>
#include <algorithm>
#define MAX 1000005
std::vector<int> mines[MAX];
int n;
int strt[MAX]; // Starting of the interval at field #i.
void cleanup() {
for (int i = 0; i <= n+1; ++i) {
mines[i].clear();
strt[i] = 0;
}
}
void read() {
int m;
scanf("%d%d", &n, &m);
for(int a, b; m--; ) {
scanf("%d%d", &a, &b);
assert (a >= 1 && a <= n);
if (b < a) continue; // There is no way we will reach field `a` before time `b`, so recording this mine is pointless.
mines[a].push_back(b);
}
for (int i = 1; i <= n; ++i)
std::sort(mines[i].rbegin(), mines[i].rend());
}
int bomb(const int field, const int start, const int end) {
// Find a bomb in field #field, between `start` and `end` time.
auto& v = mines[field];
while (!v.empty() && v.back() < start) v.pop_back();
if (v.empty() || v.back() > end) {
return 0;
}
return v.back();
}
int solve() {
// `pos` tracks the position you are currently on.
// `time` tracks the end of the time interval you must spend at the current position (tracked by `pos`).
int pos = 0, time = 0;
strt[pos] = 0; // `strt[i]` tracks the start of the time interval you must spend at position `i`.
while (pos < n + 1) {
const int b = bomb(pos, strt[pos], time);
if (b) {
// There is a bomb in this field during this range. It detonates at time `b`.
// Take one step back, and make sure to stay there until time `b`.
pos = pos - 1;
time = b;
} else {
// No bomb in this field during the interval you intend to spend here.
// Advance one step, and increase the time by 1.
pos = pos + 1;
time = time + 1;
assert(strt[pos] < time);
strt[pos] = time;
}
}
return time;
}
int main() {
int TC;
scanf("%d",&TC);
while(TC--) {
read();
printf("%d\n", solve());
cleanup();
}
return 0;
}
I2luY2x1ZGUgPGFzc2VydC5oPgojaW5jbHVkZTxzdGRpby5oPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKI2RlZmluZSBNQVggMTAwMDAwNQoKc3RkOjp2ZWN0b3I8aW50PiBtaW5lc1tNQVhdOwppbnQgbjsKaW50IHN0cnRbTUFYXTsgIC8vIFN0YXJ0aW5nIG9mIHRoZSBpbnRlcnZhbCBhdCBmaWVsZCAjaS4KCnZvaWQgY2xlYW51cCgpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IG4rMTsgKytpKSB7CiAgICAgICAgbWluZXNbaV0uY2xlYXIoKTsKICAgICAgICBzdHJ0W2ldID0gMDsKICAgIH0KfQoKdm9pZCByZWFkKCkgewogICAgaW50IG07CiAgICBzY2FuZigiJWQlZCIsICZuLCAmbSk7CiAgICBmb3IoaW50IGEsIGI7IG0tLTsgKSB7CiAgICAgICAgc2NhbmYoIiVkJWQiLCAmYSwgJmIpOwogICAgICAgIGFzc2VydCAoYSA+PSAxICYmIGEgPD0gbik7CiAgICAgICAgaWYgKGIgPCBhKSBjb250aW51ZTsgIC8vIFRoZXJlIGlzIG5vIHdheSB3ZSB3aWxsIHJlYWNoIGZpZWxkIGBhYCBiZWZvcmUgdGltZSBgYmAsIHNvIHJlY29yZGluZyB0aGlzIG1pbmUgaXMgcG9pbnRsZXNzLgogICAgICAgIG1pbmVzW2FdLnB1c2hfYmFjayhiKTsKICAgIH0KICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47ICsraSkKICAgICAgICBzdGQ6OnNvcnQobWluZXNbaV0ucmJlZ2luKCksIG1pbmVzW2ldLnJlbmQoKSk7Cn0KCmludCBib21iKGNvbnN0IGludCBmaWVsZCwgY29uc3QgaW50IHN0YXJ0LCBjb25zdCBpbnQgZW5kKSB7CiAgICAvLyBGaW5kIGEgYm9tYiBpbiBmaWVsZCAjZmllbGQsIGJldHdlZW4gYHN0YXJ0YCBhbmQgYGVuZGAgdGltZS4KICAgIGF1dG8mIHYgPSBtaW5lc1tmaWVsZF07CiAgICB3aGlsZSAoIXYuZW1wdHkoKSAmJiB2LmJhY2soKSA8IHN0YXJ0KSB2LnBvcF9iYWNrKCk7CiAgICBpZiAodi5lbXB0eSgpIHx8IHYuYmFjaygpID4gZW5kKSB7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CiAgICByZXR1cm4gdi5iYWNrKCk7Cn0KCmludCBzb2x2ZSgpIHsKICAgIC8vIGBwb3NgIHRyYWNrcyB0aGUgcG9zaXRpb24geW91IGFyZSBjdXJyZW50bHkgb24uCiAgICAvLyBgdGltZWAgdHJhY2tzIHRoZSBlbmQgb2YgdGhlIHRpbWUgaW50ZXJ2YWwgeW91IG11c3Qgc3BlbmQgYXQgdGhlIGN1cnJlbnQgcG9zaXRpb24gKHRyYWNrZWQgYnkgYHBvc2ApLgogICAgaW50IHBvcyA9IDAsIHRpbWUgPSAwOyAgCiAgICBzdHJ0W3Bvc10gPSAwOyAgLy8gYHN0cnRbaV1gIHRyYWNrcyB0aGUgc3RhcnQgb2YgdGhlIHRpbWUgaW50ZXJ2YWwgeW91IG11c3Qgc3BlbmQgYXQgcG9zaXRpb24gYGlgLgogICAgd2hpbGUgKHBvcyA8IG4gKyAxKSB7CiAgICAgICAgY29uc3QgaW50IGIgPSBib21iKHBvcywgc3RydFtwb3NdLCB0aW1lKTsKICAgICAgICBpZiAoYikgewogICAgICAgICAgICAvLyBUaGVyZSBpcyBhIGJvbWIgaW4gdGhpcyBmaWVsZCBkdXJpbmcgdGhpcyByYW5nZS4gSXQgZGV0b25hdGVzIGF0IHRpbWUgYGJgLgogICAgICAgICAgICAvLyBUYWtlIG9uZSBzdGVwIGJhY2ssIGFuZCBtYWtlIHN1cmUgdG8gc3RheSB0aGVyZSB1bnRpbCB0aW1lIGBiYC4KICAgICAgICAgICAgcG9zID0gcG9zIC0gMTsKICAgICAgICAgICAgdGltZSA9IGI7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgLy8gTm8gYm9tYiBpbiB0aGlzIGZpZWxkIGR1cmluZyB0aGUgaW50ZXJ2YWwgeW91IGludGVuZCB0byBzcGVuZCBoZXJlLgogICAgICAgICAgICAvLyBBZHZhbmNlIG9uZSBzdGVwLCBhbmQgaW5jcmVhc2UgdGhlIHRpbWUgYnkgMS4KICAgICAgICAgICAgcG9zID0gcG9zICsgMTsKICAgICAgICAgICAgdGltZSA9IHRpbWUgKyAxOwogICAgICAgICAgICBhc3NlcnQoc3RydFtwb3NdIDwgdGltZSk7CiAgICAgICAgICAgIHN0cnRbcG9zXSA9IHRpbWU7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHRpbWU7Cn0KCmludCBtYWluKCkgewogICAgaW50IFRDOwogICAgc2NhbmYoIiVkIiwmVEMpOwogICAgd2hpbGUoVEMtLSkgewogICAgICAgIHJlYWQoKTsKICAgICAgICBwcmludGYoIiVkXG4iLCBzb2x2ZSgpKTsKICAgICAgICBjbGVhbnVwKCk7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==