Exact K-Removals Palindrome Transformation

You are given a string s and an integer k. Your task is to determine whether it is possible to remove exactly k characters from s such that the remaining string is a palindrome.

A string is a palindrome if it reads the same forwards and backwards. The removal operation can delete characters from any positions in the string, and the order of the remaining characters must be preserved.

Note: If the string s is already a palindrome, you can only remove exactly k characters if either k is even or the length of s is odd. This is because, when a palindrome is reduced by a symmetric removal, the parity of removals matters.

Formally, given a string of length n, you need to check if there exists a palindromic subsequence of length n – k. In the special case that s is already a palindrome, the answer is "YES" only if k % 2 == 0 or n is odd; otherwise the answer is "NO".

You are required to process multiple test cases.

inputFormat

The input is given from standard input (stdin) and has the following format:

T
k s
k s
... (T test cases total)

Where:

• T is the number of test cases.
• For each test case, k is an integer representing the number of characters to remove, and s is a string consisting of lowercase letters.

outputFormat

For each test case, output a single line to standard output (stdout) containing either "YES" if it is possible to remove exactly k characters from s to form a palindrome, or "NO" otherwise.

## sample

3
1 abca
2 abcba
1 abcd

YES
YES
NO

</p>