solution

Bối cảnh

Trong sinh khóa cho các giao thức mật mã (Diffie-Hellman, DSA, một số biến thể RSA), người ta thường cần một số nguyên tố an toàn (safe prime) $P = 2q+1$, trong đó $q$ cũng là số nguyên tố. Khi đó $q$ được gọi là số nguyên tố Sophie Germain. Tính chất này quan trọng vì nhóm nhân $\mathbb{Z}_P^*$ có cấp $P-1 = 2q$ chỉ có ước nguyên tố là $2$ và $q$, giúp tránh các tấn công kiểu Pohlig-Hellman lên bài toán logarit rời rạc.

Đề bài

Cho một số nguyên $q$. Hãy xác định:

1. Nếu $q$ không phải số nguyên tố: in ra NOT_PRIME.
2. Nếu $q$ là số nguyên tố và $2q+1$ cũng là số nguyên tố (tức $q$ là số Sophie Germain, $2q+1$ là số nguyên tố an toàn): in ra SOPHIE_GERMAIN và giá trị $2q+1$ (cách nhau một dấu cách).
3. Nếu $q$ là số nguyên tố nhưng $2q+1$ không phải số nguyên tố: in ra PRIME_ONLY.

Ràng buộc

• $2 \le q \le 10^7$.

Ví dụ

Input:

11

Output:

SOPHIE_GERMAIN 23

Giải thích: $11$ là số nguyên tố, $2 \times 11 + 1 = 23$ cũng là số nguyên tố, nên $11$ là số Sophie Germain và $23$ là số nguyên tố an toàn tương ứng.