题目描述

你有一组 $n$ 个数字贴纸，用一个长度为 $n$ 的字符串 $S$ 表示。$S$ 中的每个字符都是数字 0 到 9，代表一张该数字的贴纸。

你想用这些贴纸制作时间显示。每个时间显示显示的格式是 HH:MM，其中：

• 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。

对于第四个测试用例，你无法制作任何时间显示。