← 返回题目列表

Codeforces · 2182/A

A. 新年串

中文机器翻译题面 查看原题

我们将调用由字符组成的字符串 0, 2, 5,和/或 6 a 新年字符串 if 至少一个 的两个条件满足:

  • 它包含字符串 2026 作为连续子串;
  • 它不包含字符串 2025 作为连续子字符串。

例如,字符串 20252026, 21026, 20262026, 000 是新年字符串。琴弦 2025, 20256, 20252025, 000202500020226 不是新年字符串。

给你一个字符串 $$$s$$$。您可以执行以下操作任意次数(可能为零):

  • 选择字符串 $$$s$$$ 中的一个字符并将其替换为 0, 2, 5,或 6 (您可以选择这四个字符中的任意一个)。

计算使字符串 $$$s$$$ 成为新年字符串所需的最少操作数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 20$$$) — $$$s$$$ 中的字符数;
  • 第二行包含 $$$s$$$ — 一系列 $$$n$$$ 字符 0, 2, 5,和/或 6.

输出

对于每个测试用例,输出一个整数 — 使字符串 $$$s$$$ 成为新年字符串所需的最少操作数。

示例

输入
复制

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

输出
复制

0
1
0
0
1
1
0

注意

在语句的第二个示例中,您可以将字符串的 $$$2$$$-nd 字符替换为 2。那么字符串就会变成 2225.

在语句的第五个示例中,您可以将第 $$$4$$$ 字符替换为 6。那么字符串就会变成 20262025.

在语句的第六个示例中,您可以将第 $$$8$$$ 字符替换为 6。那么字符串就会变成 202520266.