あなたはこれから $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]$ はこれらの単語の接頭辞となります）。各日の終了後、1日目からその日までに学習した異なる単語の総数を数えてください。

入力

入力は複数のテストケースから構成されます。入力の最初の行には、テストケースの数を示す整数 $T$ ($1 \le T \le 10^4$) が含まれます。各テストケースは以下の形式です。

最初の行には、辞書を表す長さ $n$ ($1 \le n \le 2 \times 10^5$) の小文字の英字からなる文字列 $s_1s_2 \dots s_n$ が含まれます。

2行目には、学習する日数を示す整数 $q$ ($1 \le q \le 2 \times 10^5$) が含まれます。

続く $q$ 行の各行には、2つの整数 $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$ をスペース区切りで1行に出力してください。ここで $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$ となります。

2番目のサンプルテストケースについては、1日目にすべての単語（a, aa, aaa）を学習済みであるため、答えは常に 3 となります。