Lucifer MorningStar is interested in deepest desires of Zing. Being a programmer Zing said he has a desire of knowing number of magical substrings in a string. A substring of string S is said to be magical if it contains atleast one magical character (A character is magical if its value is prime, and we assign values to characters as:  A is assigned 1 , B is assigned 2......Z is assigned 26). So you have to calculate total number of magical substrings for S in order to help Lucifer who is absolutely newbie in programming, so that he does not disappoint Zing.

Input

First line contains number of test cases. ( 1<=T<=10).

For each case input will contain two lines.

First line contains length of string N ( 1<=N<=10^5).

Second line will contain a string S of length N. (String will only contain uppercase letters.)

Output

For each test case output a single integer denoting number of magical substrings of S in new line.

Example

Input:

1

3

ABC

Output:
5