We define the distance of two strings A and B with same length n is
$dis_{A,B} = \sum\limits_{i=0}^{n-1}|A_{i}-B_{n-1-i}|$
The difference between the two characters is defined as the difference in ASCII.
You should find the maximum length of two non-overlapping substrings in given string S, and the distance between them are less then or equal to m.

The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with one integers m : the limit distance of substring.
Then a string S follow.

Limits
$T \leq 100$
$0 \leq m \leq 5000$
Each character in the string is lowercase letter, $2 \leq |S| \leq 5000$
$\sum |S| \leq 20000$

For each test case output one interge denotes the answer : the maximum length of the substring.