There are $n$ snakes in the meadow, numbered $1, 2, \dots, n$. Initially, each snake has a stamina value $a_i$. We say that snake $x$ is stronger than snake $y$ if and only if their current stamina values satisfy $a_x > a_y$, or $a_x = a_y$ and $x > y$.
The snakes will engage in a duel that lasts for several rounds. In each round, the strongest snake has the option to either eat or not eat the weakest snake:
- If it chooses to eat, the strongest snake's stamina value will be reduced by the weakest snake's stamina value, and the weakest snake is eaten and exits the duel. The next round then begins.
- If it chooses not to eat, the duel ends immediately.
Each snake wishes to eat as many other snakes as possible without being eaten itself (obviously, a snake will not choose to eat itself).
Assuming all snakes are sufficiently intelligent, determine how many snakes remain after the duel ends.
There are multiple test cases. For the first test case, the stamina of each snake is given in the input. For each subsequent test case, the stamina of some snakes is modified relative to the previous test case to form the new input.
Input
The first line contains a single positive integer $T$, representing the number of test cases.
For the first test case, the first line contains a single positive integer $n$, and the second line contains $n$ non-negative integers representing $a_i$.
For the 2nd to $T$-th test cases, each test case consists of: The first line contains a non-negative integer $k$, representing the number of snakes whose stamina is modified. The second line contains $2k$ integers, where every two integers form a pair $(x, y)$, indicating that the value of $a_x$ is changed to $y$. A position may be modified multiple times, with the final modification taking effect.
Output
Output $T$ lines, each containing a single integer representing the number of snakes remaining at the end.
Examples
Input 1
2 3 11 14 14 3 1 5 2 6 3 25
Output 1
3 1
Note 1
In the first test case, in the first round, snake 3 is the strongest and snake 1 is the weakest. If snake 3 chooses to eat, it will be eaten by snake 2 in the second round. Therefore, snake 3 chooses not to eat in the first round, and all 3 snakes survive.
In the second test case, the stamina of the 3 snakes becomes 5, 6, 25. In the first round, snake 3 is the strongest and snake 1 is the weakest. If it chooses to eat, snake 3's stamina becomes 20. In the second round, it remains the strongest snake and can eat snake 2. Therefore, snake 3 chooses to eat in both rounds, and only 1 snake remains at the end.
Input 2
2 5 13 31 33 39 42 5 1 7 2 10 3 24 4 48 5 50
Output 2
5 3
Examples 3
See snakes/snakes3.in and snakes/snakes3.ans in the contestant directory.
Examples 4
See snakes/snakes4.in and snakes/snakes4.ans in the contestant directory.
Constraints
For 20% of the data: $n = 3$. For 40% of the data: $n \le 10$. For 55% of the data: $n \le 2000$. For 70% of the data: $n \le 5 \times 10^4$. For 100% of the data: $3 \le n \le 10^6$, $1 \le T \le 10$, $0 \le k \le 10^5$, $0 \le a_i, y \le 10^9$. It is guaranteed that for every test case (including after all modifications), the $a_i$ are sorted in non-decreasing order.