Limits 1s, 512 MB

Lately Fahim is getting a lot of love letters. A LOT of love letters. Since he is confused about which ones he should read he is planning to make a short list.

As Fahim likes prime numbers a lot, he decided to read the letters from the girls who gave him love letters a prime number of times.

He now needs your help. Since he doens't want you to know the names of his admirers he is only going to give you the first letter of their names. For example instead of "Ayesha", you get "A"; instead of "Samiya", you get "S"; instead of "Monisha" you get "M"; and so on. You can assume that each letter uniquely identifies one of his admirers.

Yours job is to find the names (in this case, the first letter of the names) of the girls who sent Fahim letters a prime number of times.

Input

First line of input contains an integer Tc​ (1 ≤ Tc ≤ 100) denoting the number of test cases followed by Tc​ lines.

Each line contains an integer N​ (1 ≤ N ≤ 100000), the number of letters Fahim has received, and a string S​, the array of characters representing the admirers. All characters are in uppercase.

Output

For each case the output must maintain the following format

Case X:
A = N
B = M
C = Q

Here X ​is the number of test cases starting from 1.

A,​ B​, C, ... ​ is the list of all characters whose frequency is a prime number and N​, M​, Q​, ... are the corresponding prime numbers.

Print all characters in alphabetical order (A, B, C, D, ... Z).

If one of the admirers fulfill the condition print “Love is painful !”.

Sample

InputOutput
3
11 ADMTSADBCCA
6 SSSTAA
10 BDCADDPMDX
Case 1:
A = 3
C = 2
D = 2
Case 2:
A = 2
S = 3
Case 3:
Love is painful !

Submit

Login to submit.

Statistics

94% Solution Ratio
sarwarITEarliest, Jul '17
Paul72Fastest, 0.0s
ariful_luLightest, 131 kB
Nusab19Shortest, 233B
Toph uses cookies. By continuing you agree to our Cookie Policy.