#629 Keeping Multiple Positions

Statement

Statement language

You are given an integer sequence $A_1,A_2,\ldots,A_N$ of length $N$ . Its elements are numbered $1,2,\ldots,N$ from left to right.

While at least two elements remain, you may perform the following operation.

Let $L$ be the current length of the sequence. Choose an integer $k$ such that $2\leq k\leq L$ .
Keep only the elements whose current positions are multiples of $k$ , and delete all other elements. In other words, keep the $k$ -th, -th, -th, elements that exist in the current sequence.

For example, if the current sequence is $(8,1,9,4,7,2,3)$ and you choose $k=2$ , only the elements at positions $2$ , , and remain. The sequence becomes . If you then choose again, only , the element at , remains. You may choose a new value of for each operation. The values of the elements do not change.

Perform operations until exactly one element remains. Find the largest possible value of that final element. If $N=1$ initially, perform no operations.

Input

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the largest possible value of the final remaining element on its own line.

Constraints

$1\leq T\leq200\,000$ .
$1\leq N\leq200\,000$ .
$- 10^{}$ ().

Subtasks

#	Score	Constraints
1	27	$A_i\leq A_{i+1}$ for $1\leq i<N$ .

Samples

Sample 1

Input

1
7
8 1 9 4 3 7 2

Output

7

First, choose $k=2$ to keep the elements at positions $2$ , $4$ , and $6$ , obtaining $(1,4,7)$ . Renumber the remaining elements and choose . Only , the element at position in the current sequence, remains. Thus, two operations can leave , which is the maximum possible value.