You are given a string ~S~, and ~q~ queries.

For each query, you are given a string ~T~ and two integers ~l~, ~r~. You are asked to output the number of distinct substrings of ~T~ that is not a substring of ~S[l..r]~

String ~S[l..r]~ refers the substring of ~S~ from index ~l~ to ~r~, i.e. ~s_l s_{l+1} ... s_{r-1} s_r~.

Input Specification

The first line contains an string ~S~.

The next line contains an integer ~q~.

Each of the next ~q~ lines contains a string ~T~ and two integers ~l~, ~r~.

Output Specification

For each test case, output the answer.

Sample Input

scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9

Sample Output

12
10
4

Constraints

Case	~\mid S \mid \leq ~	~ Q \leq ~	~\sum \mid T\mid \leq~	Properties
~1~	~200~	~200~	~40000~	~T\leq 200~
~2~	~1000~	~200~	~40000~	~T\leq 200~
~3~	~1000~	~200~	~40000~	~T\leq 200~
~4~	~1000~	~200~	~5 \times 10^5~	None
~5~	~1000~	~200~	~5 \times 10^5~	None
~6~	~5 \times 10^5~	~1~	~5 \times 10^5~	None
~7~	~5 \times 10^5~	~1~	~5 \times 10^5~	None
~8~	~10^5~	~10^5~	~2 \times 10^5~	None
~9~	~10^5~	~10^5~	~2 \times 10^5~	string is random
~10~	~2 \times 10^5~	~10^5~	~4 \times 10^5~	None
~11~	~2 \times 10^5~	~10^5~	~4 \times 10^5~	String is Random
~12~	~3 \times 10^5~	~10^5~	~6 \times 10^5~	None
~13~	~3 \times 10^5~	~10^5~	~6 \times 10^5~	string is random
~14~	~4 \times 10^5~	~10^5~	~8 \times 10^5~	None
~15~	~4 \times 10^5~	~10^5~	~8 \times 10^5~	string is random
~16~	~5 \times 10^5~	~10^5~	~10^6~	None
~17~	~5 \times 10^5~	~10^5~	~10^6~	String is random
~18~	~2 \times 10^5~	~10^5~	~10^6~	None
~19~	~3 \times 10^5~	~10^5~	~10^6~	none
~20~	~4 \times 10^5~	~10^5~	~10^6~	none
~21~	~5 \times 10^5~	~10^5~	~10^6~	none
~22~	~5 \times 10^5~	~10^5~	~10^6~	none
~23~	~5 \times 10^5~	~10^5~	~10^6~	none
~24~	~5 \times 10^5~	~10^5~	~10^6~	none
~25~	~5 \times 10^5~	~10^5~	~10^6~	none

For the first ~17~ test points all queries have ~l=1,r=|S|~.

For all data, it is guaranteed that ~1\leq l \leq r \leq |S|~,~1\leq |T|\leq 5 \times 10^5~