Anna has a row of blocks, each with exactly one letter from A to Z written on it. The blocks are numbered , , ..., from left to right.
Today, she is learning about palindromes. A palindrome is a string that is the same written forwards and backwards. For example, ANNA, RACECAR, AAA and X are all palindromes, while AB, FROG and YOYO are not.
Bob wants to test how well Anna understands palindromes, and will ask her questions. The -th question is: can Anna use all of the blocks numbered from to , inclusive, rearranging them if necessary, to form a palindrome? After each question, Anna puts the blocks back in their original positions.
Please help Anna by finding out how many of Bob's questions she can answer "yes" to.
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case starts with a line containing the two integers and , the number of blocks and the number of questions, respectively. Then, another line follows, containing a string of uppercase characters (A to Z). Then, lines follow. The -th line contains the two integers to , describing the -th question.
输出格式
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of questions Anna can answer "yes" to.
For the first question, Anna must use the blocks AACC. She can rearrange these blocks into the palindrome ACCA (or CAAC).
For the second question, Anna must use the blocks A. This is already a palindrome, so she does not need to rearrange them.
For the third question, Anna must use the blocks BAAC. These blocks cannot be rearranged into a palindrome.
For the fourth question, Anna must use the blocks CA. These blocks cannot be rearranged into a palindrome.
For the fifth question, Anna must use the blocks AACCA. She can rearrange these blocks to form the palindrome ACACA (or CAAAC).
In total, she is able to answer "yes" to of Bob's questions, so the answer is .
In Sample Case #2, and . For the first question, Anna must use the blocks XYZ to create a palindrome. This is impossible, and since the rest of Bob's questions are the same as the first one, the answer is .
