Given a string S of length N containing only numeric characters, find the number of Nice Pairs.

A Nice Pair is a pair of indices - (i, j) such that 1 ≤ i < j ≤ N and j - i = |S_{j} - S_{i}|.

------ Input Format ------

• First line will contain T, number of testcases. Then the testcases follow.
• The first line of each testcase contains a single integer, N, the length of the string
• The second line of each testcase contains a string S of length N. The string contains only numeric characters [0-9]

------ Output Format ------

For each testcase, output a single integer - the number of nice pairs in the given string.

------ Constraints ------

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
- String $S$ contains only numeric characters
- The sum of $N$ over all test cases does not exceed $2\cdot10^{5}$

----- Sample Input 1 ------
3
3
123
5
13492
8
94241234

----- Sample Output 1 ------
3
2
9

----- explanation 1 ------
Test Case $1$: There are $3$ nice pairs in the given string - $(1,2) , (1,3) , (2,3)$

Test Case $2$: There are $2$ nice pairs in the given string - $(2,3) , (3,5)$

见题面

见题面