Longest Palindromic Substring

You are given a string S, and your task is to compute the length of the longest substring of S that is a palindrome. A palindrome is a string that reads the same backward as forward.

Formally, for a string S of length N, find the maximum length L such that there exists an index i with 0 ≤ i ≤ N-L and the substring S[i, i+L-1] is a palindrome. In mathematical notation, you need to calculate: (\max{L \mid \exists i,\ S[i..i+L-1] \text{ is a palindrome}}).

inputFormat

The input begins with a single integer T on the first line, representing the number of test cases. Each test case is described on a separate line that starts with an integer N (the length of the string) followed by a space and then the string S. You may assume that S contains only lowercase letters.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest palindromic substring of S.## sample

1
5 ababa

5