ASHMHF - Meet Her Fast!

no tags 

Dreamerash Lives in Wonderland. He loves a girl named Tania. They live in two different cities. Today Tania told him that she is coming to Dreamerash’s city for a work. She told him that she will stay in a hotel. But unfortunately as their communication link broke up she couldn’t tell him the exact hotel. After her arriving in the city they can again communicate with each other. Since they’ve not seen each other for a long time he wants to meet her as soon as possible after her arrival in the city. So he decides to stay in one of the hotels until he meets her.

There are n hotels in the city, all are arranged in one straight line. Dreamerash know the positions of every hotel. Positions of every hotel are distinct. He wants to stay in a hotel from where, sum of distance among all the other hotels is minimum. As he is busy dreaming, he wants you to solve this problem for him.

Your task is to find the index (starting from one) of a hotel from where, sum of distance among all the other hotels is minimum. If there are multiple hotels, print the index of the hotel that appeared in the input first.

Input

First line contains an integer T (1 ≤ T ≤ 10) denoting the number of test cases.

For each test case there will be following lines:

The first line has an integer N (1 ≤ N ≤ 10^5) denoting the number of hotels.

Next line contain array of N space separated distinct integers A[i] (1 ≤ A[i] ≤ 10^9) denoting the positions of the hotels indexed from One.

Output

For each test case print the case number followed by the index of the hotel according to the following format “Case X: I” without quote, where X denotes the case number and I denotes the index of the desired hotel.

For better understanding see the sample input output.

Example

 

Input

Output

2

4

1 12 17 9

5

8 20 60 14 32

Case 1: 2

Case 2: 2

 


 [ This problem orginally contributed by MD. Ashrafuzzaman Khan]
 

hide comments
smso: 2018-10-25 11:32:20

binary search also works

hello_world123: 2018-07-17 20:22:00

Solve this first -> https://www.spoj.com/problems/ABSP1/


Added by:Avik Sarkar
Date:2018-07-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own