# Kirinriki

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

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.

## Input

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$

## Output

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

## Sample Input

1
5
abcdefedcb

## Sample Output

5

Hint[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


liuyiding

## Source

2017 Multi-University Training Contest - Te