Trong tiết học toán, thầy giáo đưa ra một câu đố cho cả lớp và bạn nào tìm được đáp án nhanh nhất sẽ được thưởng quà và câu đố như sau:

Trong số tất cả các cặp số tự nhiên phân biệt từ ~1~ đến ~n~, hãy tìm ước số chung lớn nhất có thể có của các số nguyên trong cặp. Nói cách khác nhiệm vụ của các bạn là hãy tìm giá trị lớn nhất của ước chung lớn nhất của ~a~ và ~b~, trong đó ~a~,~b~ thuộc đoạn [~1, n~].

Sau khi nghe xong câu đố bạn Thắng cũng rất muốn nhận quà nhưng chưa tìm được đáp án. Các bạn hãy giúp bạn Thắng nhé!

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~t~ (~t ≤ 1000~), số lượng các trường chợp cần xét.
• t dòng tiếp theo, mỗi dòng chứa 1 số nguyên dương ~n~ (~2 ≤ n ≤ 10^9~)

Dữ liệu ra:

• Gồm t dòng, mỗi dòng chứa số nguyên dương là ước số chung lớn nhất của ước số chung lớn nhất của các cặp số thuộc đoạn [~1, n~]

Ví dụ:

Input

2
3
5

Output

1
2

Ở quán ăn sáng nọ có ~𝑛~ khách quen. Mỗi vị khách cứ sau một số ~𝑦~ ngày nhất định sẽ đến quán ăn đó để ăn sáng. Biết rằng xuất phát điểm ban đầu tất cả các vị khách quen sẽ đến ăn sáng vào ngày đầu tiên. Bạn hãy giúp chủ quán tính xem sau bao nhiêu ngày thì tất cả các vị khách quen của quán mới lại cùng đến ăn sáng cùng ngày và khi đó mỗi vị khách đã đến quán ăn bao nhiều lần.

Dữ liệu vào:

• Dòng đầu chứa số nguyên n (~2 ≤ 𝑛 < 100~)
• Dòng thứ hai chứa n số nguyên ~𝑦~. (~1 ≤ 𝑦 < 100~)

Dữ liệu ra:

• Dòng đâu tiên ghi ra số ngày mà tất cả các vị khách cùng đến quán ăn.
• Dòng thứ hai chứa n số là số lần một vị khách đã đến quán ăn cho tới lúc tất cả cùng đến.

Ví dụ

Input

3
2 3 4

Output

12
6 4 3

Cho một số nguyên dương ~N~, hãy biểu diễn ~N~ dưới dạng tổng của các số nguyên tố sao cho số lượng số hạng trong tổng là lớn nhất có thể.

Input

• Số nguyên dương ~N~ trên 1 dòng

Constraints

~1 \le N \le 10^{12}~

Output Format

• Dòng 1. In ra số lượng số hạng trong tổng. Nếu không thể biểu diễn ~N~ dưới dạng tổng các số nguyên tố thì in ra -1.

Sample Input 0

6

Sample Output 0

3

Sample Input 1

1

Sample Output 1

-1