We define the humor value of a string $$$t$$$ as the length of the longest palindrome string which occurs at least twice in it.

Formally, a string $$$p$$$ is humor with respect to $$$t$$$, if and only if both of the following conditions are met:

$$$p$$$ is a palindrome, and
there exist at least two different indices $$$i \in [1, |t| - |p| + 1]$$$, such that $$$t[i, i + |p| - 1] = p$$$.

The humor value of $$$t$$$ is defined as the maximum length among all humor strings with respect to $$$t$$$.

You are given a string $$$s$$$ of length $$$n$$$ which only contains lowercase Latin letters and $$$q$$$ queries. Each query contains two integers $$$l_i$$$, $$$r_i$$$, and you need to find the humor value of the string $$$s[l_i, r_i]$$$.

Here, $$$a[l, r]$$$ is defined as the string $$$a_l,a_{l+1},\ldots,a_r$$$.

Input

The first line contains two integers $$$n$$$, $$$q$$$ ($$$1\le n,q\le 5\cdot10^5$$$).

The second line contains a string $$$s$$$.

The next $$$q$$$ lines contain the description of queries. The $$$i$$$-th line contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$).

Output

On the $$$i$$$-th line, output the answer to the $$$i$$$-th query.

Note

In the first query, the following palindrome strings occur at least twice: a,aa,aaa,aaaa,b,bb,bbb. The longest one is aaaa, so the humor value is $$$4$$$.

In the second query, one of the longest humor strings with respect to $$$s[2, 7]$$$ is aa.

PalindromePalindrome

Examples