{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eConsider $n$ segments on a two-dimensional plane, where the endpoints of the $i$-th segment are $(l_i, i)$ and $(r_i, i)$. One can put as many tokens as he likes on the integer points of the plane (recall that an integer point is a point whose $x$ and $y$ coordinates are both integers), but the $x$ coordinates of the tokens must be different from each other.\u003c/p\u003e\n\n\u003cp\u003eWhat\u0027s the maximum possible number of segments that have at least one token on each of them?\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThe first line of the input contains an integer $T$ (about 100), indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains one integer $n$ ($1 \\le n \\le 10^5$), indicating the number of segments.\u003c/p\u003e\n\n\u003cp\u003eFor the next $n$ lines, the $i$-th line contains 2 integers $l_i, r_i$ ($1 \\le l_i \\le r_i\\le 10^9$), indicating the $x$ coordinates of the two endpoints of the $i$-th segment.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that at most 5 test cases have $n \\ge 100$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one integer, indicating the maximum possible number of segments that have at least one token on each of them.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3\n1 2\n1 1\n2 3\n3\n1 2\n1 1\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor the first sample test case, one can put three tokens separately on (1, 2), (2, 1) and (3, 3).\u003c/p\u003e\n\n\u003cp\u003eFor the second sample test case, one can put two tokens separately on (1, 2) and (2, 3).\u003c/p\u003e\n"}}]}