Given a String S and a character C, find the length of the longest palindromic subsequence of S containing the character C.

Input

• The First Line contains an integer T denoting the number of testcases.
• Each testcase is of 2 lines. 
  • The First line contains one character C 
  • The Second line contains the string S 

Output 

For every testcase print the maximum length on a new line.

Constraints

• 1 <= T <= 10
• 1 <= |S| <= 1000
• Both C and S are made up of small English alphabets.