Questions

Distinct Powers.

Aayush has just arrived home after his Maths Class.Today he learnt a very special thing that every number could be represented as a sum of distinct powers of 2.He was amazed when he came to know about this.

Example:

6 - > 4 + 2

11 -> 8 + 2 + 1

On his way he back home he kept testing this given property.While testing he realized that this special summation is unique for every number but it may be a subset of many other numbers.

Example :

3 -> 2+1 Thus 2+ 1 is unique for 3 but this pattern is a subset for 7 as 7 -> 4 + 2 + 1 , 11 -> 8 + 2 + 1 etc.

Since he got baffled after coming to this conclusion he asks you for help.

Given a numbers A you need to output the smallest number such that the special summation of A is subset of the special summation for that number.

Input:

The first line contains T denoting the number of test cases.

Then T lines follow each containing 1 integer A.

Output:

Print the smallest number which satisfy the above condition.

Constraints:

1 <= T <= 10000

1<= A <= 10^9

Milly and ranks

Milly is shocked after seeing her result as some of the students were given same ranks. So she started predicting ranks of her classmates. She is more interested in giving distinct ranks to all of the students. She can increase any rank by a factor of 1 any number of times. But this single operation requires 1 unit amount of thinking at a time. You are required to help her in giving distinct ranks to all of the students with utilizing minimum amount of thinking.

Input

• First line of the input will contain T denoting the number of test cases.
• For every test case, first line will contain N (No. of students). Next line will contain N space separated integers denoting Ri, rank of ith student.

Output

• For every test case, print minimum thinking utilized in a new line.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 105
• 1 ≤ Ri ≤ N

Sample Input

2

2

1 1

3

1 1 2

Sample Output

1

2

Explanation

Test case #1 : She can increase any of the one rank by 1.

Test case #2 : She can increase the rank of the first student by two times.