Taco Palindrome Transformation

You are given a string s, and two integers k and p. The task is to determine whether there exists any contiguous substring of length p in s that can be transformed into a palindrome by modifying at most k characters.

For a given substring, the minimum number of modifications needed to turn it into a palindrome can be calculated by counting the number of characters with odd frequencies. Formally, if a substring has an odd count of characters equal to odd_count, then the minimal number of changes required is \(\lfloor \frac{odd\_count}{2} \rfloor\). If this value does not exceed k for any contiguous substring of length p, output YES; otherwise, output NO.

Note: All formulas in this problem, such as the conversion formula \(\lfloor \frac{odd\_count}{2} \rfloor\), are given in \(\LaTeX\) format.

inputFormat

The first line contains an integer T representing the number of queries. Each of the next T lines contains a query with a string s and two integers k and p, separated by spaces.

outputFormat

For each query, output a single line: YES if there exists a contiguous substring of length p in s that can be turned into a palindrome by modifying at most k characters; otherwise, output NO.

## sample

5
abcde 2 3
abacaba 1 5
zzzzzz 0 4
abcdef 0 2
racecar 1 7

YES
YES
YES
NO
YES

</p>