K. Time Display Stickers
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have a collection of $$$n$$$ digit stickers, represented by a string $$$S$$$ of length $$$n$$$. Each character of $$$S$$$ 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 $$$00$$$ and $$$11$$$ (inclusive), and
  • MM is a two-digit minute between $$$00$$$ and $$$59$$$ (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?

Input

The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) representing the number of test cases. After that, $$$t$$$ test cases follow. Each of them is presented as follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

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

The sum of $$$n$$$ across all test cases in one input file does not exceed $$$10^6$$$.

Output

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

Example
Input
4
10
0123456789
11
00123456789
8
99111111
4
1234
Output
1
2
2
0
Note

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.