C. Super Palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a binary string $$$x$$$ of length $$$l(l \geq 3)$$$,we call $$$x$$$ super palindrome iff $$$x_1x_2...x_l$$$ is a palindrome and $$$x_1x_2...x_{l-2}$$$ is also a palindrome.

For example,111 and 010 are super palindromes but 1001,10100,11 are not.

You're given a binary string $$$s$$$ of length $$$n$$$.Count the number of substrings which are super palindromes in $$$s$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$($$$3 \le n \le 4 \cdot 10^5$$$).

The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot10^5$$$.

Output

For each test case, print the number of substrings which are super palindromes in $$$s$$$.

Example
Input
2
6
000010
16
0110101001111101
Output
4
13
Note

Test Case $$$1$$$:

There're $$$4$$$ substrings which are super palindromes — $$$s_1s_2s_3,s_2s_3s_4,s_1s_2s_3s_4,s_4s_5s_6$$$.