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 at least 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