题目描述

Lawliet 有一个长度为 $n$ 的数列，表示为 $a_1, a_2, \dots, a_n$，他想确定有多少种好的分割方式。

如果分割大小 $k$ 满足 $1 \leq k \leq n$，且在按分割大小将数列 $a$ 划分为多个部分后，每个子序列都是非递减的，那么分割大小 $k$ 被认为是好的分割大小。分割方式如下：

• 数列 $a$ 被划分为 $⌈\frac{n}{k}⌉$ 个部分。
• 对于第 $i$ 部分（$1 \leq i \leq ⌈\frac{n}{k}⌉ - 1$），元素为 $a_{(i-1)×k+1}, a_{(i-1)×k+2}, \dots, a_{i×k}$。
• 对于第 $⌈\frac{n}{k}⌉$ 部分，元素为 $a_{(⌈\frac{n}{k}⌉-1)×k+1}, \dots, a_n$。注意，最后一部分的长度可能小于 $k$。

Lawliet 认为这个问题太简单了，所以他将进行 $q$ 次修改。每次修改提供两个正整数 $p$ 和 $v$，表示将 $a_p$ 的值更改为 $v$。

你的任务是帮助 Lawliet 计算每次修改之前和每次修改之后的好的分割大小的数量。

输入

第一行包含一个整数 $T$（$1 \leq T \leq 10$），表示测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）和 $q$（$1 \leq q \leq 2 \cdot 10^5$），表示数列的长度和修改次数。
• 第二行包含 $n$ 个整数，表示数列 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 2 \cdot 10^9$）。
• 接下来的 $q$ 行，每行包含两个整数 $p$（$1 \leq p \leq n$）和 $v$（$1 \leq v \leq 2 \cdot 10^9$），表示将序列中的第 $p$ 个元素修改为 $v$。

保证所有测试用例中 $n$ 的总和和 $q$ 的总和均不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出 $q+1$ 行，表示每次修改之前和每次修改之后的好的分割大小数量。

样例

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

1
2
3

样例解释

初始时，唯一的好分割大小是 $k = 1$。

在第一次修改之后，数列变为 [4, 5, 2, 6, 1]。此时 $k = 1$ 和 $k = 2$ 均为好分割大小。

在第二次修改之后，数列变为 [4, 5, 5, 6, 1]。此时 $k = 1$、$k = 2$ 和 $k = 4$ 均为好分割大小。