Będziesz uczyć się słów ze słownika przez następne $q$ dni. Słownik jest ciągiem $S = s_1s_2 \dots s_n$ o długości $n$, składającym się z małych liter alfabetu angielskiego, a słowo jest podciągiem $S$.

W $i$-tym dniu nauczysz się wszystkich słów, które zaczynają się od $S[l_i : r_i] = s_{l_i}s_{l_i+1} \dots s_{r_i}$ (co oznacza, że $S[l_i : r_i]$ jest prefiksem tych słów). Po każdym dniu policz, ile różnych słów już poznałeś, licząc od pierwszego dnia.

Wejście

Dostępnych jest wiele zestawów danych testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$) określającą liczbę zestawów danych. Dla każdego zestawu danych:

Pierwsza linia zawiera ciąg $s_1s_2 \dots s_n$ o długości $n$ ($1 \le n \le 2 \times 10^5$) składający się z małych liter alfabetu angielskiego, określający słownik.

Druga linia zawiera liczbę całkowitą $q$ ($1 \le q \le 2 \times 10^5$), określającą liczbę dni, w których będziesz uczyć się słów.

Dla kolejnych $q$ linii, $i$-ta linia zawiera dwie liczby całkowite $l_i$ oraz $r_i$ ($1 \le l_i \le r_i \le n$), wskazujące, że w $i$-tym dniu nauczysz się wszystkich słów mających prefiks $s_{l_i}s_{l_i+1} \dots s_{r_i}$.

Gwarantuje się, że ani suma $n$, ani suma $q$ dla wszystkich zestawów danych nie przekroczy $2 \times 10^5$.

Wyjście

Dla każdego zestawu danych wypisz jedną linię zawierającą $q$ liczb całkowitych $c_1, c_2, \dots, c_q$ oddzielonych spacjami, gdzie $c_i$ to liczba różnych słów, których nauczyłeś się od 1. dnia do $i$-tego dnia (włącznie).

Przykład

Wejście 1

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

Wyjście 1

4 6 7
3 3 3

Uwagi

Dla pierwszego przykładowego zestawu danych:

• W 1. dniu nauczyłeś się abc, abca, abcab oraz abcabd. Zatem odpowiedź to 4.
• W 2. dniu nauczyłeś się ab, abc, abca, abcab, abcabd oraz abd. Istnieją 4 słowa, które już poznałeś, więc odpowiedź to $4 + (6 - 4) = 6$.
• W 3. dniu nauczyłeś się d, którego wcześniej nie znałeś. Zatem odpowiedź to $6 + 1 = 7$.

Dla drugiego przykładowego zestawu danych, nauczyłeś się wszystkich słów (a, aa, aaa) w 1. dniu, więc odpowiedź zawsze wynosi 3.