實力強大的小 A 被選為了 ION2018 的出題人，現在他需要解決題目的命名問題。
題目敘述
小 A 被選為了 ION2018 的出題人，他精心準備了一道品質十分高的題目，且已經把除了題目命名以外的工作都做好了。
由於 ION 已經舉辦了很多屆，所以在題目命名上也是有規定的。ION 命題手冊規定：每年由命題委員會規定一個小寫字母字串，我們稱之為那一年的命名串，要求每道題的名字必須是那一年的命名串的一個非空連續子字串，且不能和前一年的任何一道題目的名字相同。
由於一些特殊的原因，小 A 不知道 ION2017 每道題的名字，但是他透過一些特殊手段得到了 ION2017 的命名串，現在小 A 有 $Q$ 次詢問：每次給定 ION2017 的命名串和 ION2018 的命名串，求有幾種題目的命名，使得這個名字一定滿足命題委員會的規定，即是 ION2018 的命名串的一個非空連續子字串且一定不會和 ION2017 的任何一道題目的名字相同。
由於一些特殊原因，所有詢問給出的 ION2017 的命名串都是某個串的連續子字串，詳細可見輸入格式。
輸入格式
第一行一個字串 $S$，之後詢問給出的 ION2017 的命名串都是 $S$ 的連續子字串。
第二行一個正整數 $Q$，表示詢問次數。
接下來 $Q$ 行，每行有一個字串 $T$ 和兩個正整數 $l, r$，表示詢問如果 ION2017 的命名串是 $S[l..r]$，ION2018 的命名串是 $T$ 的話，有幾種命名方式一定滿足規定。
保證輸入中給出的字串都是由小寫字母構成的。
輸出格式
輸出 $Q$ 行，第 $i$ 行一個非負整數表示第 $i$ 個詢問的答案。
範例
輸入格式 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
輸出格式 1
12 10 4
範例 2
見選手目錄下的 name/name2.in 與 name/name2.ans。
子任務
| 測試點 | $\lvert S\rvert \le$ | $Q \le$ | $\sum \lvert T\rvert \le$ | 詢問限制 | 其他限制 |
|---|---|---|---|---|---|
| $1$ | $200$ | $200$ | $40000$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | $\lvert T\rvert \le 200$ |
| $2$ | $1000$ | $200$ | $40000$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | $\lvert T\rvert \le 200$ |
| $3$ | $1000$ | $200$ | $40000$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | $\lvert T\rvert \le 200$ |
| $4$ | $1000$ | $200$ | $5 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 無 |
| $5$ | $1000$ | $200$ | $5 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 無 |
| $6$ | $5 \times 10^5$ | $1$ | $5 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 無 |
| $7$ | $5 \times 10^5$ | $1$ | $5 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 無 |
| $8$ | $10^5$ | $10^5$ | $2 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 無 |
| $9$ | $10^5$ | $10^5$ | $2 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $10$ | $2 \times 10^5$ | $10^5$ | $4 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 無 |
| $11$ | $2 \times 10^5$ | $10^5$ | $4 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $12$ | $3 \times 10^5$ | $10^5$ | $6 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 無 |
| $13$ | $3 \times 10^5$ | $10^5$ | $6 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $14$ | $4 \times 10^5$ | $10^5$ | $8 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 無 |
| $15$ | $4 \times 10^5$ | $10^5$ | $8 \times 10^5$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $16$ | $5 \times 10^5$ | $10^5$ | $10^6$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 無 |
| $17$ | $5 \times 10^5$ | $10^5$ | $10^6$ | 對於所有詢問有 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $18$ | $2 \times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $19$ | $3 \times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $20$ | $4 \times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $21$ | $5 \times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $22$ | $5 \times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $23$ | $5 \times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $24$ | $5 \times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $25$ | $5 \times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
對於所有資料，保證 $1 \le l \le r \le \lvert S vert$，$1 \le \lvert T vert \le 5 imes 10^5$。