Archive Shadows

Time limit: 3000 msMemory limit: 250 MB

Two curators compare two strings: a draft strip $A$ and an old archive $B$ . A fragment of $A$ is chosen by two positions $x$ and $y$ with $1 \le x \le y \le \lvert A \rvert$ ; its text is $A_x A_{x+1} \ldots A_y$ .

A fragment is called shadowed if the same text occurs as a contiguous substring of $B$ . Otherwise, it is called fresh.

You are given $Q$ inspection ranges. For each range $[L_i, R_i]$ , count the number of pairs $(x, y)$ such that and the fragment is fresh.

Input

The first line contains a string $A$ ( $1 \le \lvert A \rvert \le 2 \times 10^5$ ). The second line contains a string $B$ (). Both strings consist only of lowercase English letters. The third line contains an integer (), the number of inspection ranges. The next lines contain descriptions of the ranges. In the -th of these lines, there are integers and ().

Output

For each inspection range, print one integer: the number of fresh fragments fully contained in that range. The answers must be printed in the same order as the input ranges.

Samples

Sample 1

Input

ababa
bab
3
1 5
1 3
2 4

Output

5
1
0

For $[1,5]$ , the fresh intervals are $(1,3)$ , $(3,5)$ , $(1,4)$ , , and . For , only is fresh. For , every fragment is shadowed.

Archive Shadows

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2