Description

There are $n$ snake on the grass, numbered from $1$ to $n$, respectively. At the begining, stamina of each snake is $a_i$. We call the snake numbered $x$ stronger than the one with number $y$ if its current stamina is greater than the other one ($a_x > a_y$), or $a_x = a_y$ and $x > y$.

Then, these snakes will have a duel. The duel will continue for several rounds. In each round, the strongest snake will have two options:

1. It will eat the weakest snake and its stamina will decreased by the stamina of that weakest snake. The eaten snake will be removed from the duel.
2. It won't eat any snake, the duel will end immediately.

Each snake wants to maximize the number of snake they eat without being eaten (obviously, snakes won't eat themselves).

Suppose every snake is smart enough, calculate the number of snake left after the duel.

This problem has multiple sets of data. For the first set of data, the stamina of each snake will be given in the input. For each subsequent set of data, some snakes' stamina will be changed.

Input Format

The first line contains an integer $T$, the number of dataset.
The following line contains a single integer $n$, the number of snakes.
The third line will contains exactly $n$ integers, the $i$-th number represents the $i$-th snake's initial stamina.
The next $T - 3$ lines contains $T - 1$ dataset, each dataset will have the following format:

• One line contains an integer $k$, the number of snakes whose stamina will be changed.
• One line contains $2k$ integers and every two integers form a pair $(x, y)$ which means that the snake number $x$'s stamina will become $y$.

Output Format

Print exactly $T$ lines, each represents the number of snakes left after the duel ends with the data provides in the $i$-th dataset.

2
3
11 14 14
3
1 5 2 6 3 25

3
1

2
5
13 31 33 39 42
5
1 7 2 10 3 24 4 48 5 50

5
3

Sample 3

See attached files snakes3.in and snakes3.in

Sample 4

See attached files snakes4.in and snakes4.in

Constraints

For $20\%$ of data, $n=3$.
For $40\%$ of data, $n \le 10$.
For $55\%$ of data, $n \le 2 \times 10^3$.
For $70\%$ of data, $n \le 5 \times 10^4$.
For $100\%$ of 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's guaranteed that in every dataset, $a_i$ will be arranged in non-decreasing order.