解题思路

我们要在字符串中出现子串 "abcdefghijklmnopqrstuvwxyz"（长度为 26，下文记为目标串 T），允许的操作是：选择一个下标把字符改成任意小写字母。问最少需要多少次操作；若无法做到输出 -1。

关键事实

• 若 n < 26，无论如何修改都不可能出现长度为 26 的子串，答案为 -1。
• 若 n ≥ 26，一定可以：选择任意长度为 26 的窗口，把其中的字符逐个改成 T 对应位置即可。因此答案等于 所有长度为 26 的窗口与 T 的最小“汉明距离”（不相等字符的个数）。

题目内容

给定一个长度为 $n$ 的字符串 $s$，字符串仅由小写字母组成，下标从 $1$ 开始。你可以对字符串执行以下操作任意次:

• 选择一个下标 $i$，将 $s_i$ 修改为任意小写字母;

请问最少需要多少次操作，才能让字符串中出现子串"$abcdefghijklmnopqrstuvwxyz$"。

【名词解释】

• 子串:子串为从原字符串中连续地选择一段字符(可以全选、可以不选)得到的新字符串。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦10^4)$，代表数据组数;

此后对于每组测试数据:

• 第一行输入一个整数 $n(1≦n≦2×10^5)$，表示字符串长度;

• 第二行输入一个长度为 $n$、仅由小写字母构成的字符串 $s$ .

除此之外，保证所有测试数据中几的总和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新起一行，输出一个整数，代表最少的操作次数;

• 如果不存在使字符串中出现完整英文字母序列的方案，则输出 $-1$ .

样例1

输入

3
37
abcdefghijklmnopqrstuvwxyzzzzzzzzzzzz
26
bcdefghijkimnopqrstuvwxyza
25
abcdefghijklmnopqrstuvwxy

输出

0
26
-1