Beauty String

You are given a string s and an integer k. Your task is to determine whether s is a beauty string. A string is called a beauty string if the length of its longest palindromic subsequence is at least k.

A palindromic subsequence is a subsequence that reads the same backwards as forwards. You need to compute the longest such subsequence and compare its length with k.

The solution typically involves using dynamic programming. A common approach is to construct a 2D DP table where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j]. The final result is "YES" if dp[0][n-1] ≥ k, otherwise "NO".

Note: If there are any formulas, use LaTeX format. For example: the transition can be written as: \(dp[i][j] = \max(dp[i+1][j],\, dp[i][j-1])\) when \(s[i] \neq s[j]\), and \(dp[i][j] = 2 + dp[i+1][j-1]\) when \(s[i] = s[j]\) (with appropriate boundary conditions).

inputFormat

The first line of the input contains an integer T representing the number of test cases.

Each of the next T lines contains a test case, each test case consists of an integer k and a string s separated by space.

Note: The input should be read from standard input (stdin).

outputFormat

For each test case, output a single line containing "YES" if the longest palindromic subsequence of s has length greater than or equal to k, otherwise output "NO".

Note: The output should be printed to standard output (stdout).

## sample

3
3 abacaba
2 abcdef
5 racecar

YES
NO
YES

</p>