K-Palindrome Checker

You are given a string s and an integer k. Your task is to determine whether the string s can be transformed into a palindrome by removing at most k characters.

A string is called a k-Palindrome if it is possible to delete at most k characters from it so that the resulting string is a palindrome. For example, by removing 1 character from "abca" (i.e. removing 'b' or 'c'), the string becomes a palindrome "aca". However, if more than k removals are necessary, the answer is "NO".

This is a classical dynamic programming problem. One approach is to compute the longest palindromic subsequence of the string and compare the number of deletions (i.e. len(s) - LPS) with k.

inputFormat

The input is given via stdin and has the following format:

• The first line contains a single integer T, the number of test cases.
• Each of the next T lines contains an integer k and a non-empty string s separated by a space.

It is guaranteed that s consists of a sequence of characters with no spaces.

outputFormat

For each test case, print a single line to stdout:

• YES if it is possible to make s a palindrome by removing at most k characters, otherwise NO.

## sample

2
1 abca
2 abcde

YES
NO

</p>