Hội đồng mới của Thượng Nghị viện có \(N\) đại biểu. Theo quy định hiện tại, hội đồng nên được chia thành các nhóm có số lượng đại biểu khác nhau và mỗi ngày mỗi nhóm phải gửi một đại biểu cho ủy ban hòa giải. Thành phần của ủy ban hòa giải nên được khác nhau mỗi ngày, nghĩa là hai ngày khác nhau nếu như có ít nhất 1 thành viên khác nhau. Nghị viện chỉ hoạt động trong khi điều này có thể được thực hiện.

Yêu cầu: hãy xác định có bao nhiêu đại biểu nên có trong mỗi nhóm để nghị viện làm việc càng lâu càng tốt.

Input

Dòng đầu tiên của đầu vào là một số nguyên \(M\), theo sau là một dòng trống và \(M\) bộ dữ liệu. Có một dòng trống ranh giới giữa các tập dữ liệu.

Mỗi bộ dữ liệu chứa một số nguyên \(N\) \((5 \leq N \leq 1000)\).

Output

Với mỗi bộ dữ liệu ghi ra trên một dòng duy nhất một số là số lượng nhóm tìm được.

Example

2
7
31

2
6