给定由 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$ 行，每行一个整数表示每个询问的答案。