Một chủ đề quan trọng hiện nay trong khoa học máy tính là mật mã. Một số thuật toán mật mã mà Mr.T đang triển khai có sử dụng các số nguyên tố lớn. Tuy nhiên, kiểm tra xem một số lớn có phải là số nguyên tố không dễ dàng như vậy. Hiện có một số thử nghiệm xác suất mang lại độ tin cậy cao với chi phí thấp. Một trong số đó là Phép thử Fermat. Cho \(a\) là một số ngẫu nhiên trong khoảng \(2\) đến \(n-1\). \(N\) là số nguyên tố nếu:

\(a^n\) \(mod\) \(n=a\)

Nếu một số vượt qua bài kiểm tra Fermat nhiều lần thì đó là số có xác suất rất cao là số nguyên tố.

Thật không may, có tin xấu. Một số số không phải số nguyên tố vẫn vượt qua bài kiểm tra Fermat với mọi số nhỏ hơn chính nó. Những con số này được gọi là số Carmichael.

Trong bài toán này, bạn được yêu cầu viết một chương trình để kiểm tra xem một số đã cho có phải là số Carmichael hay không.

Input

• Đầu vào sẽ bao gồm một nhiều dòng, mỗi dòng chứa một số dương nhỏ \(n\) \((2 \lt n \lt 65000)\).
• Nếu \(n=0\) có nghĩa là kết thúc bộ test

Output

• Với mỗi số được nhập vào, bạn phải in ra xem đó có phải là số Carmichael hay không (\(1\) là phải, \(0\) là không phải), như minh họa trong đầu ra mẫu.

Example

Sample input

1729
17
561
1109
431
0

Sample output

1
0
1
0
0