MAGSUB1 - Lucifer and Magical Substrings
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
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 |