We all know that Jan loves cookies. Right now, Jan has piles of different types of cookies in front of him: chocolate, lemon, coconut, pretzels, crackers, biscotti, macarons, lebkuchen, stroopwafels... Like any cookie lover, he wants to eat the maximum number of different types of cookies, but he has a problem: there are other people who also want to eat them. For each cookie, Jan knows what type it is and the moment someone will eat it if he doesn't do so first. The good news is that Jan can eat an unlimited number of cookies (he can even take several of the same type) and he eats them instantly. The bad news is that between two consecutive cookies, he must rest for a time proportional to the number of cookies he has eaten up to that moment. If Jan eats the first cookie at time $$$t$$$, he must wait until time $$$t+1$$$ to eat the second one. If he eats the second one at time $$$t$$$, he must wait until time $$$t+2$$$ to eat the third one. And in general, if he eats the $$$k$$$-th one at time $$$t$$$, he must wait until time $$$t+k$$$ to eat the next one.
Jan wants to eat the maximum number of different types of cookies, and your goal is to tell him what that maximum is. Nevertheless, note that Jan can eat as many cookies as he wants of the same type. Initially, Jan has an empty stomach and can eat the first cookie without having to wait. Additionally, if a cookie is going to disappear at time $$$t$$$, Jan can eat it up until that very moment $$$t$$$ (if necessary, he will snatch it from the hands of the person who was going to eat it).
The input starts with an integer $$$t$$$, the number of cases. It is followed by two integers $$$m, n$$$, the number of types of cookies and the number of cookies, respectively. Next, the $$$n$$$ cookies are described. Each one is described by two integers, $$$a_i, t_i$$$. The first indicates the type of cookie and the second the moment when the cookie will disappear if Jan does not eat it first.
Print $$$t$$$ lines, each with a single integer: the maximum number of distinct types of cookies that Jan can eat.
For all cases $$$t \leq 40$$$, $$$m \leq n$$$ and $$$1 \leq a_i \leq m$$$. Additionally, for any number between $$$1$$$ and $$$m$$$, there will be at least one cookie of that type.
Case 1: $$$ m \leq 10$$$, $$$n \leq 100$$$, $$$t_i \leq 1000$$$ (15 points)
Case 2: $$$ m \leq 10$$$, $$$n \leq 1000$$$, $$$t_i \leq 1000000$$$ (15 points)
Case 3: $$$ m \leq 100$$$, $$$n = m$$$, $$$t_i \leq 10000$$$ (20 points)
Case 4: $$$ m \leq 100000$$$, $$$n = m$$$, $$$t_i \leq 10^9$$$ (25 points)
Case 5: $$$ m \leq 50000$$$, $$$n \leq 200000$$$, $$$t_i \leq 10^9$$$ (25 points)
2 2 4 1 1 1 2 1 3 2 4 3 3 1 2 2 2 3 2
2 2
