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:

1. $p$ is a palindrome, and
2. 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.