Binary String Copying

Description:

Input:

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of $$$s$$$ and the number of copies, respectively.

The second line contains $$$n$$$ characters 0 and/or 1 — the string $$$s$$$.

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the description of the operation applied to the $$$i$$$-th copy.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$. The sum of $$$m$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output:

Print one integer — the number of different strings among $$$t_1, t_2, \ldots, t_m$$$.

Sample Input:

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

Sample Output:

3
3
1

Note:

Consider the first example. Copies below are given in order of the input operations. Underlined substrings are substrings that are sorted:

1. 101100 $$$\rightarrow$$$ 011100;
2. 101100 $$$\rightarrow$$$ 011100;
3. 101100 $$$\rightarrow$$$ 101100;
4. 101100 $$$\rightarrow$$$ 101100;
5. 101100 $$$\rightarrow$$$ 000111.

There are three different strings among $$$t_1, t_2, t_3, t_4, t_5$$$: 000111, 011100 and 101100.

Consider the second example:

1. 100111 $$$\rightarrow$$$ 100111;
2. 100111 $$$\rightarrow$$$ 001111;
3. 100111 $$$\rightarrow$$$ 001111;
4. 100111 $$$\rightarrow$$$ 010111.

There are three different strings among $$$t_1, t_2, t_3, t_4$$$: 001111, 010111 and 100111.