题目描述

我们称仅由字符 ${0,2,5,6}$ 构成的字符串为 新年字符串，当且仅当满足下列两条条件中的至少一条：

• 字符串包含子串 $\texttt{2026}$；
• 或者字符串不包含子串 $\texttt{2025}$。

例如：$\texttt{20252026}$、$\texttt{21026}$、$\texttt{20262026}$、$\texttt{000}$ 都是 新年字符串；而 $\texttt{2025}$、$\texttt{20256}$、$\texttt{20252025}$、$\texttt{000202500020226}$ 则不是。

现在给定一个长度为 $n$ 的字符串 $s$（字符均来自集合 ${0,2,5,6}$）。你可以对 $s$ 执行任意次以下操作（次数可以为 $0$）：

• 选择字符串中的某个位置，将该字符替换为 $\texttt{0}$、$\texttt{2}$、$\texttt{5}$ 或 $\texttt{6}$ 中的任意一个。

求使得字符串 $s$ 变为一个 新年字符串 的最小操作次数。

输入格式

• 第一行包含一个整数 $t$（$1\le t\le 10^4$）— 测试用例数。

• 每个测试用例包含两行：

  • 第一行包含整数 $n$（$4\le n\le 20$）— 字符串长度；
  • 第二行包含长度为 $n$ 的字符串 $s$，每个字符均为 $\texttt{0}$、$\texttt{2}$、$\texttt{5}$ 或 $\texttt{6}$。

输出格式

对每个测试用例，输出一行，包含一个整数 — 把字符串变为新年字符串所需的最小操作次数。

样例输入

7
4
0000
4
2025
4
2026
8
20252026
8
20252025
9
202520256
9
202520265

样例输出

0
1
0
0
1
1
0

说明

样例解释

• 第 $1$ 个样例：$\texttt{0000}$ 不含 $\texttt{2025}$，因此已满足“不包含 $\texttt{2025}$”这一条件，故需要 $0$ 次修改。
• 第 $2$ 个样例：$\texttt{2025}$ 包含 $\texttt{2025}$，且不包含 $\texttt{2026}$，要想成为新年字符串，至少要把一个字符改动使得**不包含 $\texttt{2025}$**或使其包含 $\texttt{2026}$。例如把第 $2$ 个字符改为 $\texttt{2}$ 得到 $\texttt{2225}$（不含 $\texttt{2025}$），因此最少需要 $1$ 次操作。