Kirinriki

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.

1
5
abcdefedcb

5

[0, 4] abcde
[5, 9] fedcb
The distance between them is abs('a' - 'b') + abs('b' - 'c') + abs('c' - 'd') + abs('d' - 'e') + abs('e' - 'f') = 5

2017 Multi-University Training Contest - Team 6