Description

In mathematics, the Lucas-Lehmer test is a primality test for Mersenne numbers (numbers of the form 2ⁿ − 1). The test was originally developed by Edouard Lucas in 1856, and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s. The well-known distributed computing project Great Internet Mersenne Prime Search (GIMPS) uses the test to locate Mersenne primes (Mersenne numbers that are also prime numbers). As of the time when this problem is composed, the largest known Mersenne prime is 2^32,382,657 − 1, which was discovered on September 4, 2006 by Curtis Cooper and Steven Boone.

The test works as follows. Let M_p = 2^p − 1 be the Mersenne number to test with p a positive integer (in real applications only large primes are of interest since primality of M_p is easy to determine when p is relatively small and if p is composite, so is M_p). Define a sequence {s_i} for all i ≥ 0 by

s₀ = 4;
s_i = s²_{i − 1} − 2 for all i > 0.

Then M_p is prime iff

s_{p − 2} ≡ 0 (mod M_p).

The number s_{p − 2} mod M_p is called the Lucas-Lehmer residue of p.

Your task is to write a simple implementation of the Lucas-Lehmer test.

Input

The input contains one or more positive integers below 8,192 which are not necessarily primes, one on a each line. End-of-file (EOF) indicates the end of input.

Output

For each integer in the input, output its Lucas-Lehmer residue in hexadecimal using digits 0 through 9 and lowercase letters a through f, each on a separate line.

59
61

64099e5fcbcaf36
0

Source

POJ Monthly--2007.08.05, frkstyc