你有一组共 $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$。

输出格式

对于每组测试用例，输出你最多可以创建的时间显示数量。

样例

输入样例 1

4
10
0123456789
11
00123456789
8
99111111
4
1234

输出样例 1

1
2
2
0

说明

对于第一组测试用例，你可以创建一个时间显示 10:59。可以证明，对于给定的贴纸集合，你无法创建两个时间显示。

对于第二组测试用例，你可以创建两个时间显示：10:59 和 04:27。

对于第三组测试用例，你可以创建两个时间显示：11:19 和 11:19。

对于第四组测试用例，你无法创建任何时间显示。