## 24 hour archive: Problem

###
** 3619
- The king's question** ** 3619 - The king's question** ** 3619 - The king's question**

#### Description

It's summer holydays and the king wants to play a little game. First he picks an integer number and writes it on his giant blackboard. Then, he keeps writing numbers in the blackboard until a number repeats. If the last number written n is even, the next one would be its half. In any other case, the next one would be 5 * n + 1. As the king is a bit lazy, when the number he is going to write is bigger or equal than M, he only writes down its residue modulo M.

After sometime, the king realizes that for some initial numbers, the sequence is too long, so he asks the following question to one of his wisest magicians:

For practical reasons, in this problem we will assume M = (1e9 + 7)^ 2 and that the number 0 never appears in the blackboard.

After sometime, the king realizes that for some initial numbers, the sequence is too long, so he asks the following question to one of his wisest magicians:

*For this initial value, how many numbers will I need to write to see the first pair of repeated numbers?*Your task of course is to write a program to help the magician, and save his life.For practical reasons, in this problem we will assume M = (1e9 + 7)^ 2 and that the number 0 never appears in the blackboard.

After sometime, the king realizes that for some initial numbers, the sequence is too long, so he asks the following question to one of his wisest magicians:

*For this initial value, how many numbers will I need to write to see the first pair of repeated numbers?*Your task of course is to write a program to help the magician, and save his life.

For practical reasons, in this problem we will assume M = (1e9 + 7)^ 2 and that the number 0 never appears in the blackboard.

After sometime, the king realizes that for some initial numbers, the sequence is too long, so he asks the following question to one of his wisest magicians:

*For this initial value, how many numbers will I need to write to see the first pair of repeated numbers?*Your task of course is to write a program to help the magician, and save his life.

For practical reasons, in this problem we will assume M = (1e9 + 7)^ 2 and that the number 0 never appears in the blackboard.

#### Input specification

In the first line you will be given a number T representing the number of tests cases to follow. In each of the following lines there will be a number n with 0 < n < 10^9. For each file the sum of the answers of all tests is never bigger than 10^9.

In the first line you will be given a number T representing the number of tests cases to follow. In each of the following lines there will be a number n with 0 < n < 10^9. For each file the sum of the answers of all tests is never bigger than 10^9.

In the first line you will be given a number T representing the number of tests cases to follow. In each of the following lines there will be a number n with 0 < n < 10^9. For each file the sum of the answers of all tests is never bigger than 10^9.

#### Output specification

Print exactly T lines, one for each test case, with the answer the magician would give to the king's question.

Print exactly T lines, one for each test case, with the answer the magician would give to the king's question.

#### Sample input

`3`

5

12

15

#### Sample output

`12`

9

16

#### Hint(s)

http://coj.uci.cu/24h/

http://coj.uci.cu/24h/

http://coj.uci.cu/24h/