[Wannafly冬令营2018Day2]Square Substrings

内存限制：512 MB 时间限制：10000 ms

小 Q 给出了一个字符串 $s_{1} s_2 \cdots s_n$ 和 $q$ 个询问 $(l_i, r_i)$。对于每个询问 $(L, R)$，他想知道字符串 $s_{L} s_{L + 1} \cdots s_R$ 有多少个子串是平方串，你能帮他解决这个问题吗？

对于字符串 $t_{1} t_2 \cdots t_m$ 来说，它的子串 $t_{x} t_{x + 1} \cdots t_y$ ($1 \leq x \leq y \leq m$) 是平方串当且仅当：

$(y - x + 1)$ 是偶数；
对于 $i = x, x + 1, \cdots, \frac{x + y - 1}{2}$，有 $t_i = t_{i + \frac{y - x + 1}{2}}$。

bb和abab以及babbab是平方串，但abba不是平方串。

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。随后的内容是各组测试数据。对于每组测试数据：

第一行包含两个整数 $n$ 和 $q$。

第二行包含一个由小写字母组成的长度为 $n$ 的字符串 $s_{1} s_2 \cdots s_n$。

在接下来的 $q$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，表示关于 $s_{l_i} s_{l_i + 1} \cdots s_{r_i}$ 的一个询问。

$1 \leq T \leq 100$
$1 \leq n, q \leq 10^6$
$1 \leq l_i \leq r_i \leq 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