Vasya vs. Delinya
As you may recall from the problem "Arnold's Bit Sequence", the schoolboy Vasya is very curious and constantly searches for new things on the Internet. Recently, Vasya was quite fortunate—he discovered Arnold's video lecture, which he watched attentively that same evening. The following day at school, during a programming elective, he devised the following problem, which he now challenges you to solve.
You are given a non-negative integer, which serves as the first term of Arnold's sequence. This number needs to be converted into its binary form, and the following operations are performed on this bit representation: for the next number in the sequence, the new value of a bit will be the sum of this bit and the next bit, taken modulo 2. Since the last bit lacks a right neighbor, Vasya, following Arnold's advice, repeats the first bit at the end to carry out the operation. Vasya was surprised to observe that at some point, the sequence generated in this manner becomes periodic—Arnold mentioned something about this, but Vasya can't quite recall...
Vasya also remembered Arnold's words from the lecture: "the outstanding American mathematician, Fields Medalist Deligne, once came to Moscow, and we discussed my other results, and he told me: "What kind of theorem is this of yours — you only considered forty million examples"…". Therefore, Vasya decided to broaden the scope of his research and learn how to quickly answer multiple queries of the type: "At which step of the described algorithm will the first term of such a periodic sequence be obtained, and what is the length of the period of this sequence?"
Assist Vasya in quickly finding answers to these queries.
Input
Each line of the input file contains a single non-negative integer n, which does not exceed 10^10—the first term of the sequence.
Output
For each query provided in the input, output the two numbers sought on a separate line, separated by a space: the step at which the first periodic term of such a periodic sequence is obtained, and the length of the period of this sequence.