Jhontu and Montu are brothers. They tend to skip study and play. So to keep them busy, a senior student of their school taught them a new game. The game is like this. There will be some folded papers in a bowl in front of them. An integer number would be written on each paper. No number will be written twice and none of them would be greater than $1,000,000$
. On each round both of them will pick a paper. They will see what number they got and then fold the paper again and put it back to the bowl. Now both of them will run an operation on their own number. If the number is odd then they will multiply it by $3$
and add $1$
to the result. But if the number is even then they will divide it by $2$
. After each such operation they will get a new number. In the next step they will apply the same operation on the new number. They will keep doing it until one of them reaches to the number $1$
. whoever reaches to $1$
first wins that round. Check the example below
Let's say, on the first round Montu's number is $256$
and Jhontu's number is $13$
. Now they will apply the operation on their own number like this.
Step - $0$ | Step - $1$ | Step - $2$ | Step - $3$ | Step - $4$ | Step - $5$ | Step - $6$ | Step - $7$ | Step - $8$ | |
---|---|---|---|---|---|---|---|---|---|
Montu | $256$ | $128$ | $64$ | $32$ | $16$ | $8$ | $4$ | $2$ | $1$ |
Jhontu | $13$ | $40$ | $20$ | $10$ | $5$ | $16$ | $8$ | $4$ | $2$ |
Montu's Number $256$
is an even number, so in the first step he divided the number by $2$
and got $128$
. On the other hand, Jhontu's number $13$
is an odd number, so in the first step he multiplied the number by $3$
and added $1$
to the result and got $40$
$(13 \times 3 + 1)$
. In $8$
steps Montu reached to $1$
. So he is the winner of this round. If both of them reach to $1$
in same number of steps then that round will be considered a draw.
First line of input will have an integer number. This is the number of timesthey played the game, $T$
. $(1 \leq T \leq 1000)$
.
Next for each game there will in $N + 1$
lines. The first line will contain an integer number $N$
. This represents the number of rounds of a particular game. $(1 \leq N \leq 1000)$
.
Next $N$
lines will have two integer numbers $a$
and $b$
, where a is Montu's number and b is Jhontu's number. $(1 \leq a \leq 1000000$
, $1 \leq b \leq 1000000)$
For each game print one line to the output. The line will start with the text “Game No i: ” where i will be replaced by the particular game number. For example, for the first game it would be “Game No 1: ”, for the second game it would be “Game No 2: ”, etc. After that there will be the number of rounds won by Montu, the number of rounds won by Jhontu and the number of rounds that were drawn in such format
Game No 1: Montu 3, Jhontu 2, Draw 0
Input | Output |
---|---|
2 5 256 13 19 12 3 4 6 7 13 14 1 12 13 | Game No 1: Montu 3, Jhontu 2, Draw 0 Game No 2: Montu 0, Jhontu 0, Draw 1 |