Given two strings $s$ and $t$ consisting only of lowercase letters $a$ and $b$, answer $q$ queries. Each query asks for the length of the longest common substring between $s[l \dots r]$ and $t$.
Input
The input consists of $q+3$ lines.
The first line contains a string $s$.
The second line contains a string $t$.
The third line contains an integer $q$.
The next $q$ lines each contain two integers $l_i, r_i$ ($1 \le l_i \le r_i \le |s|$), representing a query.
Output
The output consists of $q$ lines.
The $i$-th line represents the length of the longest common substring between $s[l_i \dots r_i]$ and $t$.
Examples
Input 1
aaba aaaabbbaa 3 1 4 1 3 2 4
Output 1
3 3 2
Subtasks
| Test Case ID | $ | s | , | t | \le$ | $q \le$ |
|---|---|---|---|---|---|---|
| $1$ | $50$ | $50$ | ||||
| $2, 3$ | $2 \times 10^3$ | $2 \times 10^3$ | ||||
| $4, 5$ | $2 \times 10^5$ | $10$ | ||||
| $6 \sim 10$ | $2 \times 10^5$ | $2 \times 10^5$ |