Alex used to be fond of numbers for long but now the thing that amuses her the most are Strings. So, she built an array (A) consisting of numbers and a string (S) of lowercase English characters and mapped each element of the array with string such that
A0 is mapped to S0 ,
A1 is mapped to S1 and so on...
At that time Betty, a friend of Alex came and asked her to find the number of substrings [i, j] ,where 'i' is strictly less than j , such that S[i] = S[j] and the sum of the array elements in the range [i+1,j-1] is equal to zero.
Alex got confused and asked for your help!
Note: If S[i] = S[j] for some (i + 1 = j) , the sum of array elements between them will be considered as 0.
\(Input :\)
- The first line of the input contains an integer T denoting the number of test cases.
- The first line of each test case contains a single integer n, the length of the string (or the array).
- The second line contains the string S.
- The third line contains n space separated integers denoting A0 to An-1
\( Output :\)
Print one integer, denoting the answer.
\(Constraints :\)
1<=T<=10
1<=n<=1000
(-100<=Ai<=100)
Problem setter: Tanya