Anany is now serving in the army. Although he is an officer, in the first a few days, he is enlisted as trooper under training. The officer in charge of his training is the officer Mohamed Yasser. Mohamed Yasser gives Anany an exercise that he must do every morning. Anany has to walk on a string of characters. He must collect one 'A', then one 'B', then one 'C', ..., and finally one 'Z' in $textbf(a l p h a b e t i c a l o r d e r)$.
As you know, Anany is lazy, which is why fate brought him to the military service. In order to minimize his walking distance, he wants to move forward only in the smallest possible substring. That is, he wants to find the smallest substring that contains all the characters in the alphabet $[ A -Z ]$ as a subsequence. Find only the length of that substring; you should let Anany depend on himself to find it.
The first line of the input contains an integer $T$ $(1 <= T <= 44)$, the number of testcases.
The first line of each testcase contains an integer $n$ $(26 <= n <= 777)$, the length of the string.
The second line contains a string $s$ consisting of uppercase English letters $(| s | = n)$.
For each test case, output one integer denoting the length of the shortest substring that contains all the characters in the alphabet $[ A -Z ]$ as a subsequence. It's guaranteed that there exist at least one such substring.
In the first test case, the solution is the substring $s [ 13 \\dots 41 ]$:
"ABCDEFDIVGHIJKLMNOPQRSTUVWXYZ".
## Input
The first line of the input contains an integer $T$ $(1 <= T <= 44)$, the number of testcases.The first line of each testcase contains an integer $n$ $(26 <= n <= 777)$, the length of the string.The second line contains a string $s$ consisting of uppercase English letters $(| s | = n)$.
## Output
For each test case, output one integer denoting the length of the shortest substring that contains all the characters in the alphabet $[ A -Z ]$ as a subsequence. It's guaranteed that there exist at least one such substring.
[samples]
## Note
In the first test case, the solution is the substring $s [ 13 \\dots 41 ]$:"ABCDEFDIVGHIJKLMNOPQRSTUVWXYZ".
**Definitions**
Let triangle $ A $ have vertices at $ (x_0, y_0) $, $ (x_0 + a, y_0) $, and $ (x_0, y_0 + b) $, with $ a > 0 $, $ b > 0 $.
**Constraints**
- $ x_0, y_0 \in \mathbb{R} $, $ -1000 \leq x_0, y_0 \leq 1000 $
- $ a, b \in \mathbb{Z}^+ $, $ 1 \leq a, b \leq 1000 $
- The line $ L: x = c $ must satisfy $ x_0 \leq c \leq x_0 + a $
**Objective**
Find $ c \in [x_0, x_0 + a] $ such that the area of the region of triangle $ A $ with $ x \leq c $ equals the area of the region with $ x > c $, i.e.,
$$
S_{\text{Left}} = S_{\text{Right}} = \frac{1}{2} \cdot \text{Area}(A)
$$
where $ \text{Area}(A) = \frac{1}{2} ab $.
The line $ x = c $ intersects the hypotenuse of the triangle (from $ (x_0 + a, y_0) $ to $ (x_0, y_0 + b) $) at point $ (c, y(c)) $, where the hypotenuse has equation:
$$
y = y_0 + b\left(1 - \frac{x - x_0}{a}\right)
$$
The left region is a polygon bounded by $ (x_0, y_0) $, $ (c, y_0) $, $ (c, y(c)) $, and $ (x_0, y_0 + b) $. Its area is:
$$
S_{\text{Left}}(c) = \frac{1}{2} (c - x_0) \left( y_0 + \left[ y_0 + b\left(1 - \frac{c - x_0}{a}\right) \right] \right) - \text{adjustment?}
$$
Actually, simpler: the left region is a trapezoid or triangle depending on $ c $, but due to the right triangle orientation, we use similarity:
The full triangle has base $ a $, height $ b $, area $ \frac{ab}{2} $.
The portion to the left of $ x = c $ is a smaller triangle similar to the original, but only if we consider the cut parallel to the y-axis. Actually, the cut creates a trapezoid and a smaller triangle on the right?
Better: The line $ x = c $ intersects the hypotenuse. The area to the left is a polygon with vertices:
$ (x_0, y_0) $, $ (c, y_0) $, $ (c, y_c) $, $ (x_0, y_0 + b) $.
But since $ (x_0, y_0 + b) $ to $ (x_0, y_0) $ is vertical, and $ (x_0, y_0) $ to $ (c, y_0) $ is horizontal, and $ (c, y_0) $ to $ (c, y_c) $ is vertical, and $ (c, y_c) $ to $ (x_0, y_0 + b) $ is along the hypotenuse — this is a quadrilateral.
Alternatively, use integration or similarity.
Let $ \Delta x = c - x_0 $. The hypotenuse: from $ (x_0 + a, y_0) $ to $ (x_0, y_0 + b) $, so slope is $ -\frac{b}{a} $.
Equation of hypotenuse:
$$
y = y_0 + b - \frac{b}{a}(x - x_0)
$$
At $ x = c $,
$$
y_c = y_0 + b - \frac{b}{a}(c - x_0)
$$
The area to the left of $ x = c $ is the area under the hypotenuse from $ x_0 $ to $ c $, minus the area below $ y = y_0 $? No — the triangle is bounded by $ x = x_0 $, $ y = y_0 $, and the hypotenuse.
Actually, the triangle is right-angled at $ (x_0, y_0) $, with legs along $ x = x_0 $ (vertical) and $ y = y_0 $ (horizontal).
So for $ x \in [x_0, c] $, the upper boundary is the hypotenuse:
$$
y_{\text{top}}(x) = y_0 + b \left(1 - \frac{x - x_0}{a}\right)
$$
The area to the left of $ x = c $ is:
$$
S_{\text{Left}}(c) = \int_{x_0}^{c} \left[ y_{\text{top}}(x) - y_0 \right] dx = \int_{x_0}^{c} b \left(1 - \frac{x - x_0}{a}\right) dx
$$
Let $ u = x - x_0 $, then:
$$
S_{\text{Left}}(c) = \int_{0}^{c - x_0} b \left(1 - \frac{u}{a}\right) du = b \left[ u - \frac{u^2}{2a} \right]_0^{c - x_0} = b \left( (c - x_0) - \frac{(c - x_0)^2}{2a} \right)
$$
Set this equal to half the total area:
$$
b \left( \Delta x - \frac{(\Delta x)^2}{2a} \right) = \frac{1}{2} \cdot \frac{ab}{2} = \frac{ab}{4}
$$
where $ \Delta x = c - x_0 $.
So:
$$
b \left( \Delta x - \frac{(\Delta x)^2}{2a} \right) = \frac{ab}{4}
$$
Divide both sides by $ b $ (since $ b > 0 $):
$$
\Delta x - \frac{(\Delta x)^2}{2a} = \frac{a}{4}
$$
Multiply both sides by $ 2a $:
$$
2a \Delta x - (\Delta x)^2 = \frac{a^2}{2}
$$
Rearrange:
$$
(\Delta x)^2 - 2a \Delta x + \frac{a^2}{2} = 0
$$
Solve quadratic:
$$
\Delta x = \frac{2a \pm \sqrt{(2a)^2 - 4 \cdot 1 \cdot \frac{a^2}{2}}}{2} = \frac{2a \pm \sqrt{4a^2 - 2a^2}}{2} = \frac{2a \pm \sqrt{2a^2}}{2} = \frac{2a \pm a\sqrt{2}}{2} = a \left(1 \pm \frac{\sqrt{2}}{2}\right)
$$
We need $ \Delta x \leq a $, so take the minus sign:
$$
\Delta x = a \left(1 - \frac{\sqrt{2}}{2}\right)
$$
Thus:
$$
c = x_0 + a \left(1 - \frac{\sqrt{2}}{2}\right)
$$
**Output**
$$
c = x_0 + a \left(1 - \frac{\sqrt{2}}{2}\right)
$$