I. Good Partitions
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Lawliet has a sequence of numbers of length $$$n$$$, denoted as $$$a_1, a_2, \ldots, a_n$$$, and he wants to determine how many good partitions exist.

A partition size $$$k$$$ is considered a good partition size if it satisfies $$$1 \leq k \leq n$$$ and, after dividing the sequence $$$a$$$ into parts by partition size, each resulting sub-sequence is non-decreasing. The partitioning method is as follows:

  • The sequence $$$a$$$ is divided into $$$\lceil \frac{n}{k} \rceil$$$ parts.
  • For the $$$i$$$-th part ($$$1 \leq i \leq \lceil \frac{n}{k} \rceil - 1$$$), the elements are $$$a_{(i - 1) \times k + 1}, a_{(i - 1) \times k + 2}, \ldots, a_{i \times k}$$$.
  • For the $$$\lceil \frac{n}{k} \rceil$$$-th part, the elements are $$$a_{(\lceil \frac{n}{k} \rceil - 1) \times k + 1}, \ldots, a_n$$$. Note that the length of the last part may be less than $$$k$$$.

Lawliet finds this problem too simple, so he will make $$$q$$$ modifications. Each modification provides two positive integers $$$p$$$ and $$$v$$$, indicating that the value of $$$a_p$$$ will be changed to $$$v$$$.

Your task is to help Lawliet calculate the number of good partition sizes before any modifications and after each modification.

Input

The first line contains an integer $$$T$$$ ($$$1\le T \le 10$$$), representing the number of test cases.

For each test case, the first line contains two integers $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) and $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$), representing the length of the sequence and the number of modifications.

The second line contains $$$n$$$ integers, representing the sequence $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 2\cdot 10^9$$$).

The following $$$q$$$ lines each contain two integers $$$p$$$ ($$$1 \le p \le n$$$) and $$$v$$$ ($$$1 \le v \le 2 \cdot 10^9$$$), indicating that the element at the $$$p$$$-th position in the sequence will be modified to $$$v$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$2\cdot 10^5$$$, respectively.

Output

For each test case, output $$$q + 1$$$ lines, representing the number of good partition sizes before any modifications and after each modification.

Example
Input
1
5 2
4 3 2 6 1
2 5
3 5
Output
1
2
3
Note

Initially, the only good partition size is $$$k = 1$$$.

After the first modification, the sequence becomes $$$[4, 5, 2, 6, 1]$$$. Both $$$k = 1$$$ and $$$k = 2$$$ are good partition sizes.

After the second modification, the sequence becomes $$$[4, 5, 5, 6, 1]$$$. The good partition sizes are $$$k = 1$$$, $$$k = 2$$$, and $$$k = 4$$$.