Bob 有一个字符串 $s_1s_2 \dots s_n$ 和 $q$ 个询问 $(l_i, r_i)$（其中 $i = 1, 2, \dots, q$）。对于每个询问 $(l_i, r_i)$，他想知道满足 $l_i \le L \le R \le r_i$ 且 $s_L s_{L+1} \dots s_R$ 是平方串的区间 $(L, R)$ 的数量。你能帮帮他吗？

一个字符串 $t_1t_2 \dots t_m$ 是平方串，当且仅当： $m$ 是偶数； $t_i = t_{i + \frac{m}{2}}$，对于所有 $i = 1, 2, \dots, \frac{m}{2}$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。接下来描述所有测试用例。对于每个测试用例： 第一行包含两个整数 $n$ 和 $q$。 第二行包含一个长度为 $n$ 的小写字母字符串 $s_1s_2 \dots s_n$。 接下来的 $q$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，表示一个询问。

• $1 \le T \le 100$
• $1 \le n, q \le 10^6$
• $1 \le l_i \le r_i \le n$
• 所有测试用例中 $n$ 的总和不超过 $10^6$
• 所有测试用例中 $q$ 的总和不超过 $10^6$

输出格式

对于每个测试用例，首先输出一行 “Case #x:”，其中 $x$ 是从 1 开始的测试用例编号。 然后，对于每个询问，输出一行整数，表示该询问的答案。

样例

输入 1

1
7 5
ababbab
1 4
2 5
3 6
4 7
1 7

输出 1

Case #1:
1
1
1
1
3

说明

bb、abab 和 babbab 是平方串，而 abba 不是平方串。