D. Decrypting the Password
time limit per test
1.2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yessine was trying to log into his email when he realized that he forgot his password. Fortunately, he wrote it in a text file and saved it just in case. However, when he opened the file, he didn't find the password but rather a very long string of digits. He then remembered that he didn't write the password but rather an encryption of it. As a matter of fact, the password is the number of substrings whose numerical representation is divisible by 11. Yessine wants to open his email, help him decrypt the password.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

The first line contains one integer $$$t \ (1 \le t \le 10^6) $$$ — the number of test cases.

The first line of each test case contains one integer $$$n \ (1 \le n \le 10^6)$$$ — the length of the string $$$s$$$.

The second line of each test case contains a string consisting of $$$n$$$ decimal digits.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$

Output

Print one line containing the answer: The number of substrings whose decimal representation is divisible by $$$11$$$

Example
Input
4
3
121
4
1111
6
123456
8
20654301
Output
1
4
0
3
Note
  • In the first case, the only substring divisible by 11 is 121
  • In the second case, the string $$$1111$$$ contains 3 substrings whose decimal representation is $$$11.$$$ Also $$$1111=11\times 101$$$ is divisible by $$$11.$$$ Finally we can verify that $$$111$$$ is not divisible by $$$11.$$$ Therefore, the total number of such substrings is $$$4.$$$