GPT - Ước chung lớn nhất trong tam giác Pascal
Giới hạn- Thời gian: 0.21s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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) 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ử (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 9 .
Example
Input:5
2
3
4
5
6 Output:2
3
2
5
1
- Người up: racer