Palindrome is a text which is read from left to right and from right to left the same. For example, 121 is a palindromic number. 122 is not a palindromic number because it becomes 221 when it is read from right to left.

Assume that, distortion is allowed until certain value (k). For example, if k is 1, 122 can be accepted as palindrome because with 1 correction it can be turned to be a palindrome. On the other hand, 1234 cannot be a palindrome number if only 1 distortion is allowed. It may be turned to a palindrome if two distortions are allowed. Note: Assume that uppercase and lowercase chars may be accepted the same.

Question: Write a program that reads a text with the number of distortions allowed for each. Return how many of them are accepted as palindromes with the given number of distortions.

Input specification: You will be given an integer (n) in the beginning. The following n lines will have an integer (k) and a string with at most 2000 characters long where 0 ≤ k ≤ 100 and 0 < n < 1000.

Output specification: Show one integer, the number of Palindrome-k numbers (or palindrome-k text).

Explanation: SEven can be turned to a palindrome if 1 distortion is applied. However, 122 is not a Palindrome number because no distortions (0) are allowed. Thus only SEven is palindrome-k text.