Giải bài trực tuyến

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 (n ≥ 0) 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)ⁿ. 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ử (với 0 ≤ k ≤ n).

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 ≤ T ≤ 20.

-       2 ≤ n ≤ 10⁹.

Example

Input:
5
2
3
4
5
6

Output:
2
3
2
5
1