You are given a number say N, you have to say minimum base B, on which this is a valid number. For example 10 is valid number in decimal (base 10) representation as well as in binary (base 2). For number 10, your answer should be 2, as this is minimum base.

Note:

Definition of Base: Base is the number of unique digits, including zero, used to represent numbers in a positional numeral system. For example, for the decimal system (the most common system in use today) the base is ten, because it uses the ten digits from 0 through 9.

Input

First line begins with T giving number of test cases. For each test case, first line begins with L, giving the length of number, then L lines follows Ni, denoting each digit of number in array format.

Note: there will be no leading zeros I.e. N(0) will not be 0.

Constraints

1 <= T <= 5

2 <= L <= 9

0 <= Ni <= 9

Output

For each case of input, print one line of output denoting the minimum base (B) representation for that number.

Example

Input:
1
2
1
0

Output:
2