给定一个字符串 $$$s$$$,由 $$$n$$$ 字符 0 和/或 1 组成。
你制作该字符串的 $$$m$$$ 个副本,令第 $$$i$$$ 个副本为字符串 $$$t_i$$$。然后,您对每个副本执行一次操作:对于第 $$$i$$$ 个副本,对其子字符串 $$$[l_i; 进行排序; r_i]$$$(从第 $$$l_i$$$ 个字符到第 $$$r_i$$$ 个字符的子字符串,包括两个端点)。请注意,每个操作仅影响一个副本,每个副本仅受一个操作影响。
你的任务是计算 $$$t_1, t_2, \ldots, t_m$$$ 中不同字符串的数量。请注意,只有在操作后至少有一个副本保持不变的情况下,才应计算初始字符串 $$$s$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 分别是 $$$s$$$ 的长度和副本数。
第二行包含 $$$n$$$ 字符 0 和/或 1 — 字符串 $$$s$$$。
然后是 $$$m$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 应用于第 $$$i$$$ 副本的操作的描述。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
打印一个整数 — $$$t_1, t_2, \ldots, t_m$$$ 中不同字符串的数量。
示例
输入 #1
3 6 5 101100 1 2 1 3 2 4 5 5 1 6 6 4 100111 2 2 1 4 1 3 1 2 1 1 0 1 1
输出 #1
3 3 1
注意
考虑第一个例子。以下副本按输入操作的顺序给出。带下划线的子字符串是已排序的子字符串:
1. 101100 $$$\rightarrow$$$ 011100;
2. 101100 $$$\rightarrow$$$ 011100;
3. 101100 $$$\rightarrow$$$ 101100;
4. 101100 $$$\rightarrow$$$ 101100;
5. 101100 $$$\rightarrow$$$ 000111。
$$$t_1、t_2、t_3、t_4、t_5$$$ 中有三个不同的字符串:000111、011100 和 101100。
考虑第二个例子:
1. 100111 $$$\rightarrow$$$ 100111;
2. 100111 $$$\rightarrow$$$ 001111;
3. 100111 $$$\rightarrow$$$ 001111;
4. 100111 $$$\rightarrow$$$ 010111。
$$$t_1、t_2、t_3、t_4$$$ 中有三个不同的字符串:001111、010111 和 100111。