题目描述

如果一个只包含字符 $0$、$2$、$5$ 和（或）$6$ 的字符串满足以下至少一个条件，我们称它为新年字符串（New Year string）：

• 它包含连续的子串 $2026$；
• 它不包含连续的子串 $2025$。

例如，字符串 $20252026$、$21026$、$20262026$、$000$ 都是新年字符串。而字符串 $2025$、$20256$、$20252025$、$000202500020226$ 都不是新年字符串。

现在给定一个字符串 $s$。你可以进行任意次（可以为 $0$ 次）如下操作：

• 选择 $s$ 中的一个字符，将其替换为 $0$、$2$、$5$ 或 $6$ 中的任意一个字符。

请计算，将字符串 $s$ 变为新年字符串所需的最小操作次数。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的组数。

每组测试数据包括两行：

• 第一行包含一个整数 $n$（$4 \leq n \leq 20$），表示字符串 $s$ 的长度；
• 第二行包含一个长度为 $n$ 的字符串 $s$，只包含 $0$、$2$、$5$、$6$ 这四种字符。

输出格式

对于每个测试用例，输出一个整数，表示将字符串 $s$ 变为新年字符串所需的最小操作次数。

说明/提示

在样例的第二个测试中，你可以将字符串的第 2 个字符替换为 2，此时字符串变为 $2225$。

在样例的第 5 个测试中，你可以将第 4 个字符替换为 $6$，则字符串变为 $20262025$。

在样例的第 6 个测试中，你可以将第 8 个字符替换为 $6$，则字符串变为 $202520266$。

由 ChatGPT 5 翻译

样例

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

0
1
0
0
1
1
0