说明

Lawliet 拥有一个长度为 $n$ 的数字序列 $a_1, a_2, \ldots, a_n$，他希望知道「好数字」的个数。

定义一个整数 $k$ 是「好数字」，如果它满足以下条件：

• $1 \leq k \leq n$；
• 将序列 $a$ 依据 $k$ 按照以下划分方法分成若干份后，每一份序列都是单调不降的。

划分方法为：

• 将序列 $a$ 分成 $\lceil \frac{n}{k} \rceil$ 份；
• 对于第 $i$ 份（$1 \leq i \leq \lceil \frac{n}{k} \rceil - 1$），包含的元素是 $a_{(i - 1) \times k + 1}, a_{(i - 1) \times k + 2}, \ldots, a_{i \times k}$；
• 对于第 $\lceil \frac{n}{k} \rceil$ 份，包含的元素是 $a_{(\lceil \frac{n}{k} \rceil - 1) \times k + 1}, \ldots, a_n$。

Lawliet 认为这个问题太过简单了，于是他会进行 $q$ 次修改，每次修改会给出两个正整数 $p$ 和 $v$，然后将 $a_p$ 的数值修改为 $v$。

Lawliet 需要你帮助计算，对于未进行任何修改前以及序列 $a$ 每次修改后，满足上述条件的「好数字」的个数。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10$），代表测试组数。

对于每组测试数据，第一行包含两个整数 $n$（$1 \le n \le 2 \cdot 10^5$）和 $q$（$1 \le q \le 2 \cdot 10^5$），分别表示序列的长度和修改次数。

第二行包含 $n$ 个整数，表示序列 $a_1, a_2, \ldots, a_n$（$1\le a_i\le 2\cdot 10^9$）。

接下来的 $q$ 行，每行包含两个整数 $p$（$1 \le p \le n$）和 $v$（$1 \le v \le 2 \cdot 10^9$），表示将序列中的第 $p$ 个位置的元素修改为 $v$。

单个测试点中 $n$ 之和与 $q$ 之和均不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出 $q + 1$ 行，分别代表未进行任何修改前以及序列 $a$ 每次修改后，序列中的「好数字」的个数。

1
5 2
4 3 2 6 1
2 5
3 5

1
2
3