我们将调用由字符组成的字符串 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$$$ 成为新年字符串所需的最少操作数。
示例
输入复制
740000420254202682025202682025202592025202569202520265
输出复制
0100110
注意
在语句的第二个示例中,您可以将字符串的 $$$2$$$-nd 字符替换为 2。那么字符串就会变成 2225.
在语句的第五个示例中,您可以将第 $$$4$$$ 字符替换为 6。那么字符串就会变成 20262025.
在语句的第六个示例中,您可以将第 $$$8$$$ 字符替换为 6。那么字符串就会变成 202520266.