VISIBLEBOX - Decreasing Number of Visible Box

no tags 

Shadowman loves to collect box but his roommates woogieman and itman don't like box and so shadowman wants to hide boxes as many as possible. A box can be kept hidden inside of another box if and only if the box in which it will be held is empty and the size of the box is at least twice as large as the size of the box.

Print the minimum number of box that can be shown.

Input

The input set starts with single line integer T (1<=T<=50) the number of test cases. Then following T cases starts with an integer N (1<=N<=100000) denoting the number of box. The next line contains N space separated positive integer. i-th of them contains a numbers Ai(1<=Ai<=100000) size of the i-th box.

Output

Output the the case number and the minimum number of box that can be shown.

Example

Input:
2
4
1 2 4 8
4
1 3 4 5

Output:
Case 1: 1
Case 2: 3

hide comments
Admin Deepak Baghel: 2016-06-12 16:22:02

Easy O(max(A(i))) solution :)

Baojun Wang: 2016-01-31 08:46:17

time limit too strict except c/c++

Last edit: 2016-01-31 08:46:48
manitejavarma: 2015-12-23 12:54:25

Is the given input sorted or not?

gomathi ganesan: 2015-12-07 12:47:49

Last edit: 2015-12-31 07:43:17
Vipul Srivastava: 2015-12-03 10:08:36

Last edit: 2015-12-03 10:32:35
Shubham Gupta: 2015-12-02 05:38:45

Few points to be noted: The input array given is not in sorted order. Do maintain a tag/index/map for a counter of each element.
Sample:
Input:
2
4
1 1 1 4
8
1 1 1 1 3 4 4 6

Output:
3
4


Added by:imranziad
Date:2015-11-25
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB CS Fest 2015 (Mokaddesh Rashid Shovon)