You’re going to learn words from a dictionary for the next $q$ days. The dictionary is a string $S = s_1s_2 \dots s_n$ of length $n$ consisting of lower-cased English letters, and a word is a substring of $S$.

On the $i$-th day, you will learn all the words which start with $S[l_i : r_i] = s_{l_i}s_{l_i+1} \dots s_{r_i}$ (that is to say, $S[l_i : r_i]$ is a prefix of these words). After each day, count how many different words you have already learned starting from the first day.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case:

The first line contains a string $s_1s_2 \dots s_n$ of length $n$ ($1 \le n \le 2 \times 10^5$) consisting of lower-cased English letters, indicating the dictionary.

The second line contains an integer $q$ ($1 \le q \le 2 \times 10^5$), indicating the number of days you’ll learn words.

For the following $q$ lines, the $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$), indicating that on the $i$-th day, you will learn all the words with a prefix of $s_{l_i}s_{l_i+1} \dots s_{r_i}$.

It’s guaranteed that neither the sum of $n$ nor the sum of $q$ of all test cases will exceed $2 \times 10^5$.

Output

For each test case, output one line containing $q$ integers $c_1, c_2, \dots, c_q$ separated by a space, where $c_i$ is the number of different words you have learned from the 1-st day to the $i$-th day (both inclusive).

Examples

Input 1

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

Output 1

4 6 7
3 3 3

Note

For the first sample test case:

• On the 1-st day you learned abc, abca, abcab, and abcabd. So the answer is 4.
• On the 2-nd day you learned ab, abc, abca, abcab, abcabd, and abd. There are 4 words you have already learned, so the answer is $4 + (6 - 4) = 6$.
• On the 3-rd day you learned d, which you haven’t learned before. So the answer is $6 + 1 = 7$.

For the second sample test case, you have learned all the words (a, aa, aaa) on the 1-st day, so the answer is always 3.