F. Find Rewards from RAPL
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ active coders in RAPL. A few months ago, the RAPL ministry took an initiative to provide daily reward points to all the active coders of RAPL. Initially, the $$$i$$$-th active coder had reward point $$$a_i$$$. From that moment $$$m$$$ days have passed. Each day the reward point of one participant was updated. On the $$$k$$$-th day $$$r_k$$$ point is added to the reward point of of $$$p_k$$$-th $$$(1 \le k \le m)$$$ active coder. These updates are recorded by the information ministry of RAPL.

Now the preservation ministry of RAPL assigned you a task. You have to collect the record of updates from the information ministry of RAPL and write a code to find the number of distinct reward points after the update of the $$$k$$$-th day and submit it to the education ministry of RAPL.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 10^{5})-$$$ the number of test cases.

The first line of each test case consists of two space separated integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 10^{5}, 1 \le m \le 10^{5})-$$$ the number of active coders, the number of days respectively.

Then $$$m$$$ line contains two space separated integers $$$p_k$$$ and $$$r_k$$$ $$$(1 \le p_k \le n, -10^{9} \le r_k \le 10^{9})$$$.

It is guaranteed that the sum of $$$n$$$, sum of $$$m$$$ over all test cases doesn't exceed $$$2.10^5$$$.

Output

For each testcase print $$$m$$$ lines. The $$$k$$$-th line contains an integer which is the number of distinct reward points after the update of $$$k$$$-th day.

Example
Input
3

5 3
20 10 25 5 3
5 2
2 -5
4 20

1 3
100
1 400
1 1
1 -100

4 5
1000000000 -294967296 705032704 -1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
Output
4
3
3
1
1
1
4
4
4
4
4
Note

Blank lines in sample input are for demonstration only. Original input file has no blank line.