Problem Description

给定由 `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) $

Input

第一行一个整数 $t\ (1\le t\le 5)$ 代表数据组数。

对于每组数据:

第一行输入一个串 $s\ (1\le |s|\le 5\times 10^5)$ 。

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

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

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

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

保证所有测试数据 $\sum |s|\le5\times 10^5,\sum q\le5\times 10^5$ 。

Output

对于每组数据输出 $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