该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

输入 T(≤1e6) 表示 T 组数据。所有数据的 n 之和 ≤2e6，m 之和 ≤2e6。

每组数据输入 n(1≤n≤2e6) m(1≤m≤2e6) 和长为 n 的 01 字符串 s。

然后输入 m 个操作，每个操作输入两个下标 i 和 j (1≤i≤j≤n)。

每次操作，复制一份 s，记作 t，然后把 t[i] 到 t[j] 排序，即区间 [i,j] 内的 0 排在 1 的前面。 这 m 次操作可以得到多少个不同的字符串？

Format

Input

输入 T(≤1e6) 表示 T 组数据。所有数据的 n 之和 ≤2e6，m 之和 ≤2e6。

每组数据输入 n(1≤n≤2e6) m(1≤m≤2e6) 和长为 n 的 01 字符串 s。

然后输入 m 个操作，每个操作输入两个下标 i 和 j (1≤i≤j≤n)。

Output

每行输出一组数据对应的答案。

Samples

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

3
3
1

Limitation

1s, 1024KiB for each test case.