Schoolboy Vasya is very inquisitive and always looking for something new to the Internet. More recently, Vasya lucky - he found the \href{http://elementy.ru/lib/430178/430281}{video lectures} of Arnold, which is the same evening carefully watched. The next day at school on the course on programming, he came up with the following puzzle, which offers you to solve. Given a non-negative integer - this is the first term of the sequence of Arnold. Now, this number should be written in binary notation, and received over the bit representation of the following operations: in the next sequence number of the new bit value is equal to the sum of this and subsequent bits modulo \textbf{2}. Since the last bit is not the right neighbor, then Vasya to perform the operation attributed, on the recommendation of the same Arnold, at the end of the first bit again. Vasya was surprised to see that at some stage obtained in this way the sequence is periodic - and Arnold seems something about this, too, told me, but Vasya has is not exactly remember ... Vasya interested in such questions as: At what step of the algorithm described above will be the first term of a periodic sequence and what is the length of the period of this sequence. Vasya Help to find answers to his questions. \InputFile The only non-negative integer \textbf{n}, not exceeding \textbf{10^8}, - the first term of the sequence. \OutputFile In a single line output required two numbers, separated by spaces: the step of obtaining first member of such a periodic and a periodic sequence of period length of the sequence.