You are given a string \(S\) consisting of lowercase Latin letters. You have to select a substring say \(S_1\) and prefix say \(S_2\) from \(S\) of equal length.

Your task is to concatenate them such that one of them is appended in reverse order and form a string \(P\) that is either:

• \(P = S_1 + \text{reverse}(S_2)\) or \(S_2 + \text{reverse}(S_1)\), here \(+\) operator denotes concatenation

If string \(P\) is a palindrome, then it is said to be a special palindrome.

Find the number of strings \(S_1\) such that there exists a prefix \(S_2\) using which a special palindrome string can be formed.

Input format

• The first line contains an integer \(T\) denoting the number of test cases.
• The first line of each test case contains an integer \(N\) denoting the length of string \(S\).
• The second line of each test case contains string \(S\).

Output format

For each test case, print the number of distinct special palindrome strings possible in a new line.

Constraints