solution

Bối cảnh

Trong RSA, số mũ công khai $e$ thường được chọn là một số nguyên tố Fermat nhỏ — tức số có dạng $2^{2^k}+1$ — vì khi đó $e-1$ là một lũy thừa của $2$, giúp phép lũy thừa modulo (mã hóa) chỉ cần các bước bình phương liên tiếp (thuật toán square-and-multiply rất hiệu quả). Các giá trị $e$ phổ biến trong thực tế là $3, 5, 17, 257, 65537$ — tất cả đều là số nguyên tố Fermat đã biết.

Đề bài

Cho một số nguyên $e$. Hãy phân loại:

1. Nếu $e$ không phải số nguyên tố: in ra NOT_PRIME.
2. Nếu $e$ là số nguyên tố và $e - 1$ là một lũy thừa của $2$ (tức $e-1 = 2^t$ với $t \ge 0$ nguyên nào đó — bao gồm cả $e-1=1=2^0$): in ra VALID_RSA_EXPONENT.
3. Nếu $e$ là số nguyên tố nhưng $e-1$ không phải lũy thừa của $2$: in ra PRIME_NOT_FERMAT.

Ràng buộc

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

Ví dụ

Input:

17

Output:

VALID_RSA_EXPONENT

Giải thích: $17$ là số nguyên tố và $17 - 1 = 16 = 2^4$, nên $17$ là một số mũ công khai RSA hợp lệ theo tiêu chí trên.