Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef calls a sequence good if it does not contain any two adjacent identical elements.

Initially, Chef has a sequence $a_{1}, a_{2}, \ldots, a_{N}$. He likes to change the sequence every now and then. You should process $Q$ queries. In each query, Chef chooses an index $x$ and changes the $x$-th element of the sequence to $y$. After each query, can you find the length of the longest good subsequence of the current sequence?

Note that the queries are not independent.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Q$.
The second line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.
$Q$ lines follow. Each of these lines contains two space-separated integers $x$ and $y$ describing a query.

------ Output ------
After each query, print a single line containing one integer ― the length of the longest good subsequence.

------ Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ a_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ x ≤ N$
$1 ≤ y ≤ 10^{9}$

------ Subtasks ------
Subtask #1 (35 points): $Q = 1$

Subtask #2 (65 points): original constraints

----- Sample Input 1 ------
1

5 2

1 1 2 5 2

1 3

4 2
----- Sample Output 1 ------
5

3

见题面

见题面