Longest Common Substring Queries

Given two strings s and t consisting only of lowercase letters a and b, and q queries, each query asks for the length of the longest common substring between the substring s[l...r] and t.

Here, a substring is a contiguous sequence of characters within a string.

The formula for the recurrence used in determining the length of the longest common substring is $$ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1] + 1, & \text{if } s[i-1] = t[j-1] \\ 0, & \text{otherwise} \end{cases} $$ where i and j are 1-indexed positions in the corresponding strings.

inputFormat

The input consists of:

1. A string s.
2. A string t.
3. An integer q representing the number of queries.
4. q lines each containing two integers l and r, representing the bounds (1-indexed) of the substring in s.

outputFormat

For each query, output a single line containing the length of the longest common substring between s[l...r] and t.

sample

aba
aba
2
1 2
2 3

2
2