#216603. [ICPC 2026 APC] Time Display Stickers

You have a collection of digit stickers, represented by a string of length . Each character of is a digit 0 through 9, representing one sticker of that digit.

You want to create time displays using these stickers. Each time display shows a time in the format HH:MM, where:

• HH is a two-digit hour between and (inclusive), and
• MM is a two-digit minute between and (inclusive).

In other words, each time display requires exactly four stickers: two for the hours and two for the minutes. Each sticker can only be used for at most one time display.

What is the maximum number of time displays you can create?

The first line of input contains one integer ( ) representing the number of test cases. After that, test cases follow. Each of them is presented as follows.

The first line of each test case contains an integer ( ).

The second line contains a string of length , consisting only of digits 0–9.

The sum of across all test cases in one input file does not exceed .

For each test case, output the maximum number of time displays you can create.

样例输入 1

4
10
0123456789
11
00123456789
8
99111111
4
1234

样例输出 1

1
2
2
0

Explanation for the sample input/output #1

For the first test case, you can create one time display 10:59. It can be shown that you cannot create two displays for a given collection of stickers.

For the second test case, you can create two time displays: 10:59 and 04:27.

For the third test case, you can create two time displays: 11:19 and 11:19.

For the fourth test case, you cannot create any time displays.