Shreya recently got an invite to the secret agency membership, called GYM. However, there's a problem she needs to solve before she could get an entry.
"Given a character C and a string S (can be a combination of 'a'-'z' or 'A'-'Z'), you need to find the GYM pair. The GYM pair consists of two numbers. The first number is the maximum size of palindromic subsequence that can be formed with S. The second number of the GYM pair is the maximum count of the character C among all the palindromic subsequences in S of the maximum size obtained above."
Can you help Shreya find the GYM pair?
Input Format:
The first line of input contains T, the number of test cases.
Each test case contains a character C, followed by a string S.
Output Format:
For each test case print the GYM pair, seperated by a space.
Constraints:
1 ≤ T ≤ 1000
1 ≤ |S| ≤ 1000
Test Case 1: In the first test case, the maximum palindromic subsequence size is 7. Since there's only one palindromic subsequence of size 7: "haereah", the maximum count of letter h is 2.
