MAGSUB1 - Lucifer and Magical Substrings

no tags 

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

hide comments
smso: 2021-11-17 07:30:03

One more testcase:
1
4
ABCA
8


Added by:hg__
Date:2019-06-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem