Description

Given two strings $s, t$ that contain only lowercase letters $a, b$, there are $q$ queries. In each query, ask for the length of the longest common substring of $s[l \dots r]$ and $t$.

Input Format

The input has $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 one query.

Output Format

Output has $q$ lines.

The $i$-th line is the length of the longest common substring of $s[l_i \dots r_i]$ and $t$.

aaba
aaaabbbaa
3
1 4
1 3
2 4

3
3
2

Hint

Translated by ChatGPT 5