承 b022，串串睜開眼睛後，發現他還在作惡夢。
現在，惡魔貓男帶著一群很長數字來追殺他。其中，質數是他們的將領。只有找出這些討人厭的質數，才能順利醒來。
所以，請你試設計一程式，有效率地判別一長整數是否為質數。

輸入格式

輸入不超過 426 行。 每行有一非負整數 \( n \) ，且  \( n < 2^{64} \)。 請讀至 EOF。 

輸出格式

對於每一個 \( n \) ，當 \( n \) 為質數時輸出 'T'，否則輸出 'F'。

範例輸入

1111111111111111111
4611686014132420609
688846502588399
68721049609
99194853094755497
8828119010022395329
2305843009213693951
2147483649
2147483647
948769699487

範例輸出

T
F
T
F
T
F
T
F
T
F

提示

範例說明

• \( 1111111111111111111 \) 是個「循環質數」
• \( 4611686014132420609 = 2147483647^2 \) 
• \( 688846502588399 \) 是個「盧卡斯質數」
• \( 68721049609 = 262147 ^ 2 \)
• \( 99194853094755497 \) 是個「費波那西質數」
• \( 8828119010022395329 = 2971215073^2 \)
• \( 2305843009213693951 \) 是個「梅森質數」
• \( 2147483649 = 3 * 715827883 \)
• \( 2147483647 \) 是個「雙梅森質數」
• \( 94879469 = 31 * 3461 * 8842957 \)

你說這些質數是不是很可愛？？>\\<

注意事項

1. 本題採「嚴格比對」，不過應該沒有任何影響
2. 本題為單筆多點的測資，請讀至 EOF，送出前請三思
3. 本題輸入為小於 \( 2^{64} \) 之整數，建議使用 uint64_t
4.  敝 OJ 支援 __uint128_t，歡迎多加利用
5. 強烈建議在本機端跑一次範例測資並通過測試執行再提交 o'_'o