你將在接下來的 $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。