Exactly K Deletions to Form Palindrome

You are given a string S and a positive integer K. The task is to determine whether it is possible to obtain a palindrome from S by deleting exactly K characters. In other words, if we let n be the length of S and L be the length of the longest palindromic subsequence of S, then you should output "YES" if and only if

\(n - L = K\)

Otherwise, output "NO".

Note: The longest palindromic subsequence problem can be solved using dynamic programming, where the recurrence is given by:

\(dp[i][j] = \begin{cases} 1 & \text{if } i = j, \\ dp[i+1][j-1] + 2 & \text{if } S[i] = S[j], \\ \max(dp[i+1][j], dp[i][j-1]) & \text{otherwise.} \end{cases}\)

You need to check if the minimum number of deletions required to make S a palindrome is exactly K.

inputFormat

The input is given in the following format from stdin:

T
S1 K1
S2 K2
... 
ST KT

where T is the number of test cases. Each of the following T lines contains a string S and an integer K separated by a space.

outputFormat

For each test case, output a single line from stdout containing either "YES" if it is possible to form a palindrome by deleting exactly K characters, or "NO" otherwise.

## sample

3
abcde 2
abbca 1
abc 1

NO
YES
NO

</p>