Tam giác Pascal là một cách sắp xếp hình học của các hệ số nhị thức vào một tam giác. Hàng thứ ~n~ ~\left(n \geq 0\right)~ của tam giác bao gồm các hệ số trong khai triển của đa thức ~f(x,y) = (x + y)^n~. Hay nói cách khác, phần tử tại cột thứ ~k~, hàng thứ ~n~ của Tam giác Pascal là ~C_n^k~, tức tổ hợp chập ~k~ của tập ~n~ phần tử ~\left(0 \leq k \leq n\right)~.

Dưới đây là hình vẽ thể hiện các hàng từ ~0~ đến ~16~ của Tam giác Pascal:

Cho số tự nhiên ~n~. Hãy tính ~GPT(n)~ là ước chung lớn nhất của các số nằm giữa hai số ~1~ trên hàng thứ ~n~ của Tam giác Pascal.

Input

Dòng đầu ghi ~T~ là số lượng test. ~T~ dòng tiếp theo, mỗi dòng ghi một số nguyên ~n~.

Output

Gồm ~T~ dòng, mỗi dòng ghi ~GPT(n)~ tương ứng.

Giới hạn

• ~1 \leq T \leq 20~.
• ~2 \leq n \leq 10^{9}~ .

Sample Input

5

2

3

4

5

6

Sample Output

2
3
2
5
1