B. Card Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A game is being played where the player (you) must guess the number the other player is thinking of. To do this, there is a set of 60 cards that contain an infinite list of numbers; the player who thinks of a number must choose all the cards where their number appears. And, to make the game fair, the number they are thinking of must be positive and less than or equal to $$$10^{18}$$$.

Below is the content of the first 5 cards:

  1. $$$1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, ...$$$
  2. $$$2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27, 30, 31, 34, 35, 38, 39, ...$$$
  3. $$$4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31, 36, 37, 38, 39, ...$$$
  4. $$$8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, 43, ...$$$
  5. $$$16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 48, 49, 50, 51, ...$$$

And so on until reaching card number 60.

The game is played in $$$q$$$ rounds. In each round, a list of $$$k$$$ numbers is given, indicating all the cards that contain the number the other player is thinking of. You must guess the secret number in each round.

Input

The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 1000$$$), indicating the number of rounds to be played.

The next $$$q$$$ lines start with an integer $$$k$$$ ($$$1 \leq k \leq 60$$$), indicating the number of cards in the round. Then, $$$k$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 60$$$) separated by a space are presented, indicating the card number $$$i$$$. It is guaranteed that there will be no repeated cards in the same round.

Output

For each of the $$$q$$$ rounds, print one line with the secret number the other player was thinking of.

It is guaranteed that the answer will always be a number in the range $$$[1, 10^{18}]$$$.

Example
Input
4
4 1 2 3 4
2 1 2
3 1 3 4
7 3 6 9 10 22 29 45
Output
15
3
13
17592456577828