Given a string $S$ and $q$ queries of the form $l,r$, find the length of the shortest string that, when repeated some number of times, exactly forms the substring $S[l...r]$.
### Input
- The first line contains the string $S$.
- The second line contains an integer $q$.
- The next $q$ lines each contain two integers $l$ and $r$.
### Output
- Print $q$ integers, each being the answer to the corresponding query.
### Constraints
- $1 \le |S| \le 5 \times 10^5$.
- $1 \le q \le 10^6$.
### Example
Input:
```
8
aaabcabc
3
1 3
3 8
4 8
```
Output:
```
1
3
5
```
Explanation:
- Query 1: Repeating the string `a` three times results in the string `aaa`.
- Query 2: Repeating the string `abc` two times results in the string `abcabc`.
- Query 3: Repeating the string `abcab` one time results in the string `abcab`.
