单点时限: 2.0 sec
内存限制: 512 MB
给定一个长度为$n(1 \leq n \leq 10^5)$ 的字符串$s$，字符串下标从1开始。
给出 $m(1 \leq m \leq 10^5)$次询问，每次询问给定两个数$l,r (1\leq l \leq r \leq n)$，删除$s_ls_{l+1}…s_{r-1}s_r$后，得到的两个字符串$s_1s_2…s_{l-1}$和$s_{r+1}s_{r+2}…s_{n}$各自有多少种不同的回文子串。
第一行，一个数$T(1 \leq T \leq 10^5)$。
每组数据第一行一个整数$n$，表达字符串长度。
第二行一个字符串$s$。
第三行一个整数$m$，表示询问次数。
接下来$m$行，每行两个整数$l,r$，表示要删除的子串左右端点。
数据保证$\sum n \leq 5\times 10^5, \sum m \leq 5 \times 10^5$
对于每组数据，输出共$m$行，每行两个数，分别表示两个字符串$s_1s_2…s_{l-1}$和$s_{r+1}s_{r+2}…s_{n}$不同的回文子串种数。
3 3 cab 2 1 2 2 3 7 caccbcc 2 3 5 4 5 4 baca 2 1 2 3 3
0 1 1 0 2 2 3 2 0 2 2 1