플린드롬 만들기

길이 $N$의 문자열 $S$가 주어진다. $S$의 각 문자는 알파벳 대문자 또는 마침표 . 이다.

$S$의 모든 마침표를 알파벳 대문자로 바꾸어 문자열 $X$를 만든다. 처음부터 알파벳 대문자였던 문자는 바꿀 수 없다.

모든 정수 $i$ ($1 \leq i \leq N$)에 대하여, $X$의 접두사 $X[1..i]$가 팰린드롬이어야 한다. 팰린드롬은 앞에서 읽은 문자열과 뒤에서 읽은 문자열이 같은 문자열이다.

조건을 만족하는 서로 다른 문자열 $X$의 개수를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $S$

각 테스트 케이스마다 조건을 만족하는 서로 다른 문자열 $X$의 개수를 한 줄에 출력한다.

• $1 \leq T \leq 100\,000$.
• $1 \leq N \leq 100\,000$.
• 모든 테스트 케이스에 대한 $N$의 합은 $100\,000$ 이하이다.
• $|S|=N$.
• $S_i$는 알파벳 대문자 또는 마침표 . 이다 ($1 \leq i \leq N$).