Вам предстоит изучать слова из словаря в течение следующих $q$ дней. Словарь представляет собой строку $S = s_1s_2 \dots s_n$ длины $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$), указывающее количество тестовых случаев. Для каждого тестового случая:

Первая строка содержит строку $s_1s_2 \dots s_n$ длины $n$ ($1 \le n \le 2 \times 10^5$), состоящую из строчных латинских букв, представляющую словарь.

Вторая строка содержит целое число $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

Пример 2

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$.

Для второго примера: вы выучили все слова (a, aa, aaa) в 1-й день, поэтому ответ всегда равен 3.