题目描述

给定由 a, b 两种小写字母组成的串 $s$, 下标从 $1$ 开始。

定义 $occ(t)$ 表示字符串 $t$ 在 $s$ 中出现的次数。

有 $q$ 次询问，每次询问有如下两种类型:

1. 操作 $1$，给定 $l,r$，询问有多少本质不同的串 $t$，满足 $s[l,r]$ 是 $t$ 的子串，且 $occ(s[l,r])=occ(t)$

2. 操作 $2$，给定 $l,r$，询问有多少本质不同的串 $t$，满足 $t$ 是 $s[l,r]$ 的子串，且 $occ(s[l,r])=occ(t)$

输入格式

第一行一个整数 $T$ ($1≤T≤5$) 代表数据组数。

对于每组数据:

第一行输入一个串 $s$ ($1≤|s|≤5×10^5$) 。

第二行一个整数 $q$ ($1≤q≤5×10^5$) 表示有 $q$ 次询问。

接下来 $q$ 行每行三个数 $op,l_0,r_0$ ($op∈ \{1,2\},1≤l_0,r_0≤|s|$)，分别表示询问的类型和询问的区间 $[l,r]$ 。

其中 $l=(l_0+lastans−1)\%|s|+1,r=(r_0+lastans−1)\%|s|+1$，保证 $1≤l≤r≤|s|$。

$lastans$ 代表上一次询问的答案，特别的对于每组数据的第一次询问时 $lastans=0$。

保证所有测试数据 $∑|s|≤5×10^5,∑q≤5×10^5$。

输出格式

对于每组数据输出 $q$ 行，每行一个整数表示每个询问的答案。

输入样例

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

输出样例

1
2
2
3
1
9
2
6
1
1