Making a Pelindrome

You are given a string $S$ of length $N$. Each character of $S$ is either an uppercase English letter or a period ..

Construct a string $X$ by replacing every period in $S$ with an uppercase English letter. Characters that are already uppercase letters cannot be changed.

For every integer $i$ ($1 \leq i \leq N$), the prefix $X[1..i]$ must be a palindrome. A palindrome reads the same from left to right and from right to left.

Find the number of distinct strings $X$ satisfying the condition.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $S$

For each test case, print the number of distinct strings $X$ satisfying the condition on one line.

• $1 \leq T \leq 100\,000$.
• $1 \leq N \leq 100\,000$.
• The sum of $N$ over all test cases does not exceed $100\,000$.
• $|S|=N$.
• $S_i$ is an uppercase English letter or a period . ($1 \leq i \leq N$).