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 (ti, 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 (sl_i, r_i). Here, (al, r) is defined as the string (a_l,a_{l+1},\ldots,a_r). 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)). On the (i)-th line, output the answer to the (i)-th query. 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 (s2, 7) is aa .