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 A_i(1<=A_i<=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