You are given a string S of the length n consisting of only lowercase English alphabets.

If the two consecutive characters in a subsequence have a difference that is no more than k, then it is called a special subsequence. Find the length of the longest special subsequence.

Input format

•  First line: t (number of test cases) 
•  Next t line: Three space-separated integers n, k, and S 

Output format

For each test case, print the length of the longest special subsequence in a new line.

Constraints

\(1 \le t \le 10\)

\(1 \le n \le 10^{5}\)

\(1 \le k \le 26\)