시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

You are trying to build an army of snowmen. To do so, you have gathered a bunch of snowballs of varying sizes. You want to build each snowman by stacking three snowballs on top of each other. You will do this by choosing a snowball to be the base. Then you will choose a smaller snowball to be the middle. Then an even smaller snowball will be the top. Each snowball has a diameter d. When evaluating a snowman, suppose the diameter of the bottom snowball is db, the diameter of the middle snowball is dm, and of the top snowball dt. Then you want the following inequalities to hold:

  • 2db ≥ 3dm
  • 2dm ≥ 3dt

Calculate the maximum number of snowmen that can be built from the available snowballs and according to the criteria.

입력

The first line is the number K of input data sets, followed by the K data sets, each of the following form:

The first line of each data set contains the number of snowballs N, where 3 ≤ N ≤ 1000. This followed by a line containing N integers each at least 1 and at most 1000. The ith integer is the diameter of the ith snowball.

출력

For each data set, output “Data Set x:” on a line by itself, where x is its number. On the next line, output the maximum number of proper snowmen that can be completed. Each data set should be followed by a blank line.

예제 입력

2
6
3 5 1 2 6 4
6
3 5 1 3 6 4

예제 출력

Data Set 1:
2

Data Set 2:
1

힌트