5732. 促融共竞

输入格式

第一行，一个数$T(1\le T\le {10}^5)$。

每组数据第一行一个整数$n$，表达字符串长度。

第二行一个字符串$s$。

第三行一个整数$m$，表示询问次数。

接下来$m$行，每行两个整数$l,r$，表示要删除的子串左右端点。

数据保证$\sum n\le 5\times {10}^5,\sum m\le 5\times {10}^5$

输出格式

对于每组数据，输出共$m$行，每行两个数，分别表示两个字符串$s_1{s}_2\dots s_{l-1}$和$s_{r+1}{s}_{r+2}\dots 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