배수로 밀기

길이가 $N$인 정수 수열 $A_1,A_2,\ldots,A_N$이 주어진다. 수열의 원소에는 왼쪽부터 $1$번, $2$번, $\ldots$, $N$번의 번호가 붙어 있다.

수열에 원소가 두 개 이상 남아 있는 동안 다음 연산을 할 수 있다.

1. 현재 수열의 길이를 $L$이라고 할 때, $2\leq k\leq L$인 정수 $k$를 하나 고른다.
2. 현재 수열에서 번호가 $k$의 배수인 원소만 남기고 나머지 원소를 모두 지운다. 즉, $k$번째, 번째, 번째, 원소 중 수열 안에 있는 원소만 남긴다.

예를 들어 현재 수열이 $(8,1,9,4,7,2,3)$일 때 $k=2$를 고르면, $2$번째, $$번째, 번째 원소만 남아 수열이 가 된다. 이 수열에서 다시 를 고르면, 인 만 남는다. 연산할 때마다 는 새로 고를 수 있으며, 원소의 값 자체는 바뀌지 않는다.

원소가 정확히 하나 남을 때까지 연산하려고 한다. 마지막에 남는 원소의 값으로 가능한 최댓값을 구하여라. 처음부터 $N=1$이면 연산을 하지 않는다.

입력은 다음 형식으로 주어진다.

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

각 테스트 케이스마다 마지막에 남는 원소의 값으로 가능한 최댓값을 한 줄에 출력한다.

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