Longest Palindromic Substring Length

You are given one or more test cases, each consisting of a list of strings. For each string, your task is to determine the length of the longest substring that is a palindrome.

A palindrome is a string that reads the same forward and backward. Mathematically, for a string s of length n, a substring s[i...j] (with 1 ≤ i ≤ j ≤ n) is a palindrome if:

$$s[i] = s[j],\ s[i+1] = s[j-1],\ \ldots$$

Your goal is to output, for each string in a test case, the value $$L = \max_{1 \leq i \leq j \leq n}\{ (j-i+1) \;|\; s[i \ldots j] \text{ is a palindrome} \}.$$

Note that each test consists of several strings, and you must process all of them.

## inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer T, the number of test cases.
2. For each test case:
   1. The first line contains an integer N, the number of strings in this test case.
   2. The next N lines each contain a non-empty string.

All strings consist only of lowercase English letters.

## outputFormat

For each test case, output one line containing N integers separated by a single space. Each integer is the length of the longest palindromic substring of the corresponding string.

The output is written to standard output (stdout).

## sample

2
1
abba
1
abcde

4
1

$$