← 返回题目列表

Codeforces · 2206/K

K. 时间显示贴纸

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

您有 $$$n$$$ 数字贴纸的集合,由长度为 $$$n$$$ 的字符串 $$$S$$$ 表示。 $$$S$$$的每个字符都是一个数字 0 通过 9,代表该数字的一张贴纸。

您想要创建 时间显示 使用这些贴纸。每次显示以以下格式显示时间 时:分,其中:

  • HH 是 $$$00$$$ 和 $$$11$$$(含)之间的两位数小时,并且
  • MM 是 $$$00$$$ 和 $$$59$$$(含)之间的两位数分钟。

换句话说,每次显示都需要四个贴纸:两个用于小时,两个用于分钟。每张贴纸最多只能展示一次。

您最多可以创建多少个时间显示?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) 表示测试用例的数量。之后,$$$t$$$ 测试用例如下。它们各自介绍如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。

第二行包含长度为$$$n$$$的字符串$$$S$$$,仅由数字组成 0–9.

一个输入文件中所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出您可以创建的最大时间显示数。

示例

输入
复制

4
10
0123456789
11
00123456789
8
99111111
4
1234

输出
复制

1
2
2
0

注意

示例输入/输出 #1 的说明

对于第一个测试用例,您可以创建一次显示 10:59。可以证明,您无法为给定的贴纸集合创建两个显示。

对于第二个测试用例,您可以创建两个时间显示: 10:59 和 04:27.

对于第三个测试用例,您可以创建两个时间显示: 11:19 和 11:19.

对于第四个测试用例,您无法创建任何时间显示。