Description

给定一个字符串\(S\)和\(q\)组询问\((x, k)\)，问前缀\(S[1..x]\)的非平凡第\(k\)长border的长度。

一个串\(T\)称为\(S\)的border，如果\(T\)既是\(S\)的前缀又是后缀。\(S\)是其本身的平凡border，其他的border是非平凡的border。

Input

• 第一行两个正整数\(n, q\)，表示字符串长度和询问个数。
• 第二行一个仅包含小写字母的字符串。
• 接下来\(q\)行每行两个正整数\(x, k\)，表示一组询问。

Output

• \(q\)行，对应\(q\)个询问的答案。如果不存在这样的border，输出\(0\)。

Sample

Input

5 4
ababa
3 1
3 2
5 1
5 2

Output

1
0
3
1

Hint

• \(n, q\le 100000\)