Description

1. A group of n students are arranged to sit in a circular table.
We assume that student j (mod n) is sitting on the
right of student j+1 (mod n).

2. Each student is given some amount of candies initially.
In particular, let A[1...n] be an array such that A[j] denotes
the candies of student j have, and the value A[j] is set to
a certain number at the beginning.

3. Then we repeat the following procedures until all students have the
same number of candies:

(i) [everyone-gets-even-candies]
If a student has odd number of candies, the student receives
one extra candy from the teacher. Else, no change.
(ii) [everyone-passes-half]
Each student passes half of his/her candies to the student on
its right.

Example: n = 3, A[1] = 2, A[2] = 4, A[3] = 8.

In the first round:
student 1 passes one candy to student 3;
student 2 passes two candies to student 1;
student 3 passes four candies to student 2.

After the first round, the array A is updated to:
A[1] = 3, A[2] = 6, A[3] = 5;

In the second round:
We first make the entries of A even:
A[1] = 4, A[2] = 6, A[3] = 6;

Next, the passing step:
student 1 passes two candies to student 3;
student 2 passes three candies to student 1;
student 3 passes three candies to student 2.

After the second round, the array A is updated to:
A[1] = 5, A[2] = 6, A[3] = 5;

In the third round:
We first make the entries of A even:
A[1] = 6, A[2] = 6, A[3] = 6;

Next, the passing step:
student 1 passes three candies to student 3;
student 2 passes three candies to student 1;
student 3 passes three candies to student 2.

After the third round, the array A is updated to:
A[1] = 6, A[2] = 6, A[3] = 6;

Now everyone gets the same number of candies, and we stop.

Input

The first line contains the number t of test cases.
Each test case is described by
(i) the number n of students and
(ii) a sequence of n integers for A[1...n].

Case 1. 1<=t<=3, 1<=n<=10, 1<=A[j]<=10
Case 2. 2<=t<=6, 1<=n<=20, 1<=A[j]<=20
Case 3. 3<=t<=9, 1<=n<=50, 1<=A[j]<=50
Case 4. 4<=t<=10, 1<=n<=100, 1<=A[j]<=100

Output

The output contains t lines.
Each line prints the number of candies of student 1 (A[1]) when we stop.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss