你将在接下来的 $q$ 天里从一本字典中学习单词。字典是一个长度为 $n$ 的字符串 $S = s_1s_2 \dots s_n$，由小写英文字母组成，单词定义为 $S$ 的子串。

在第 $i$ 天，你将学习所有以 $S[l_i : r_i] = s_{l_i}s_{l_i+1} \dots s_{r_i}$ 为前缀的单词（即 $S[l_i : r_i]$ 是这些单词的前缀）。在每一天结束后，请统计从第一天开始到当天为止，你已经学习过的不同单词的总数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个长度为 $n$ ($1 \le n \le 2 \times 10^5$) 的字符串 $s_1s_2 \dots s_n$，由小写英文字母组成，表示字典。

第二行包含一个整数 $q$ ($1 \le q \le 2 \times 10^5$)，表示你学习单词的天数。

接下来的 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)，表示在第 $i$ 天，你将学习所有以 $s_{l_i}s_{l_i+1} \dots s_{r_i}$ 为前缀的单词。

保证所有测试数据的 $n$ 之和以及 $q$ 之和均不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出一行包含 $q$ 个整数 $c_1, c_2, \dots, c_q$，用空格分隔，其中 $c_i$ 表示从第 $1$ 天到第 $i$ 天（包含首尾）你已经学习过的不同单词的总数。

样例

输入 1

2
abcabd
3
1 3
1 2
6 6
aaa
3
3 3
2 3
1 3

输出 1

4 6 7
3 3 3

说明

对于第一组样例测试数据：

• 在第 1 天，你学习了 abc, abca, abcab 和 abcabd。所以答案是 4。
• 在第 2 天，你学习了 ab, abc, abca, abcab, abcabd 和 abd。你已经学习过的单词共有 4 个，所以答案是 $4 + (6 - 4) = 6$。
• 在第 3 天，你学习了 d，这是你之前没学过的。所以答案是 $6 + 1 = 7$。

对于第二组样例测试数据，你在第 1 天就已经学习了所有单词 (a, aa, aaa)，因此答案始终为 3。