ASHMHF - Meet Her Fast!

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 position 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 ≤ 105) denoting the number of hotels.

Next line contain array of N space separated distinct integers A[i] (1 ≤ A[i] ≤ 109) 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:
2
4
1 12 17 9
5
8 20 60 14 32

Output:
Case 1: 2
Case 2: 2

[ This problem originally contributed by MD. Ashrafuzzaman Khan]


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

hide comments
2018-10-25 11:32:20
binary search also works
2018-07-17 20:22:00
Solve this first -> https://www.spoj.com/problems/ABSP1/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.