一个星球上有 $n$ 个国家，编号为 $1\sim n$。

对于每个 $1\leq i<n$，第 $i$ 号国家与第 $i+1$ 号国家互为盟友。特别的，第 $1$ 号国家和第 $n$ 号国家也互为盟友。

现在有一条消息需要在星球上进行传播。初始时有一些国家知道该消息，有一些国家不知道。

你作为星球的统领者，每天可以进行如下两种传播操作之一：

• 指定一个国家，告诉该国家消息。该操作会让被指定的一个国家知道该消息。
• 让所有已经知道该消息的国家告知他们的所有盟友。该操作会使当前至少有一个“已知消息盟友”的国家知道该消息。

你想知道至少需要多少天才能让所有国家都知道该消息。

接下来还有 $q$ 次修改操作，每次给定 $op,l,r$，表示进行如下修改：

• 若 $op=1$，则将编号为 $l\sim r$ 的所有国家都设置为初始时知道该消息。
• 若 $op=2$，则将编号为 $l\sim r$ 的所有国家都设置为初始时不知道该消息。

每次操作之后，你都需要求出至少需要多少天才能让所有国家都知道该消息。注意，你并不会真正进行传播操作。

输入格式

本题有多组数据。第一行一个正整数 $T$（$1\leq T\leq 5$）表示数据组数。对于每组测试数据：

第一行输入两个整数 $n,q$（$1\leq n,q\leq 2\cdot 10^5$），表示国家数量和修改次数。

第二行输入一个长度为 $n$ 的只包含字符 $0$ 和 $1$ 的字符串 $s$，若 $s$ 的第 $i$ 个字符是 $0$，则表示第 $i$ 个国家最初不知道该消息，否则表示第 $i$ 个国家最初知道该消息。

接下来 $q$ 行，每行三个整数 $op,l,r$（$1\leq op\leq 2,1\leq l\leq r\leq n$），表示一次修改操作。

保证 $\sum n,\sum q\leq 5\cdot 10^5$。

输出格式

对于每组测试数据，输出 $q$ 行，每行一个整数，表示每一次修改之后的答案。

样例

输入

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

输出

1
2
2
1
2