Shortest Palindrome Extension

You are given a string s of length N. Your task is to determine the length of the shortest palindrome that can be obtained by adding the minimum number of characters at the beginning or at the end of s.

A string is a palindrome if it reads the same forward and backward. In mathematical terms, a string s is a palindrome if \( s = s^R \), where \( s^R \) represents the reversal of s.

Example:

• For s = "abc", the shortest palindrome formed is "abcba" of length 5.
• For s = "aabb", one possible shortest palindrome is "baabba" of length 6.

Note that you are not required to output the palindrome itself, only its length.

inputFormat

The input begins with an integer T denoting the number of test cases. Each test case consists of two lines:

1. An integer N representing the length of the string.
2. A string s of length N.

You can assume that s contains no spaces.

outputFormat

For each test case, output a single line containing one integer — the length of the shortest palindrome that can be formed by adding the minimum number of characters to s.

## sample

2
3
abc
4
aabb

5
6

</p>