An integer sequence $b_1, b_2, \ldots, b_n$ is good if $\operatorname{mex}(b_1, b_2, \ldots, b_n) - (b_1 | b_2 | \ldots | b_n) = 1$. Here, $\operatorname{mex(c)}$ denotes the MEX$^{\text{∗}}$ of the collection $c$, and $|$ is the bitwise OR operator.

Shohag has an integer sequence $a_1, a_2, \ldots, a_n$. He will perform the following $q$ updates on $a$:

• $i$ $x$ — increase $a_i$ by $x$.

After each update, help him find the length of the longest good subarray$^{\text{†}}$ of $a$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two space-separated integers $n$ and $q$ ($1 \le n, q \le 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n$).

The next $q$ lines of each test case are of the following form:

• $i$ $x$ ($1 \le i, x \le n$) — it means you should increase $a_i$ by $x$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$ and the sum of $q$ doesn't exceed $10^5$.

Output

For each test case, output $q$ lines — on the $i$-th line output the length of the longest good subarray of $a$ after the $i$-th update.

见题面 Input 部分

见题面 Output 部分

In the first test case, after the first update, the array becomes $[0, 0, 1, 0, 1, 1]$, and here the whole array is good because $\operatorname{mex}([0, 0, 1, 0, 1, 1]) - (0 | 0 | 1 | 0 | 1 | 1) = 2 - 1 = 1$.

After the second update, the array becomes $[0, 0, 3, 0, 1, 1]$, and here the subarray $[0, 1, 1]$ has the maximum length among all the good subarrays.

Finally, after the third update, the array becomes $[0, 0, 3, 0, 1, 4]$, and here the subarrays $[0, 0]$ and $[0, 1]$ both have the maximum length among all the good subarrays.