Counting Repeated Prefix Patterns

You are given a string (S). There are (q) queries. In each query you are given two integers (i) and (k). Let (S[1,i]) denote the prefix of (S) of length (i). For each query, count the number of non-empty strings (A) such that there exist (possibly empty) strings (B_1, B_2, \dots, B_{k-1}) satisfying

[ S[1,i] = A,B_1,A,B_2,A,\dots,B_{k-1},A. ]

In other words, if you split (S[1,i]) into exactly (k) copies of (A) interleaved with arbitrary strings (which may be empty), how many choices of (A) (with (|A| > 0)) exist? Note that when (k = 1), the equation becomes (S[1,i] = A), so there is exactly one possibility.

inputFormat

The first line contains a non-empty string \(S\) consisting of lowercase English letters.

The second line contains an integer \(q\) \((1 \le q \le 10^5)\) representing the number of queries.

Each of the next \(q\) lines contains two integers \(i\) and \(k\) \((1 \le i \le |S|,\; 1 \le k \le 10^5)\) separated by a space.

outputFormat

For each query, output a single integer representing the number of non-empty strings \(A\) satisfying the given condition for the prefix \(S[1,i]\). Each answer should be printed on a new line.

sample

aba
2
3 1
3 2

1
1