408532: GYM103182 A Corporate Issues

After a long day of work, $$$q$$$ corporate workers across the world are angry and want to get home as soon as possible. Luckily, all they have to do is to walk in a straight line. For each corporate worker $$$i$$$, let $$$N_i$$$ be the position of their workplace and $$$1$$$, the position of their home.

Corporate employees can move in three ways:

• take a step forward (move from position $$$i$$$ to position $$$i-1$$$)
• take a step back (move from position $$$i$$$ to position $$$i+1$$$)
• if they are at a position $$$i$$$ such that $$$i$$$ is a multiple of 3, channel all of their fury into a jump so great that their position will be divided by three (move from position $$$i$$$ to position $$$i/3$$$)

However, it is not a joke. They really want to get home quickly. Therefore, to calm them down, each corporate worker must be told the minimum number of movements that they have to make in order to get home. Moreover, they must be told in how many different ways they can minimize the number of movements. That way, they are sure to calm down!

Formally, you are given $$$q$$$ queries - each of them representing a worker. For each worker, you start at a position $$$N_{i}$$$. Given the starting position, what are the minimum number of moves that the worker will need to get to position 1? Moreover, in how many ways can he get home in the minimum amount of moves?

The first line consists of an integer $$$q$$$ ($$$1 \leq q \leq 10^{3}$$$), representing the number of corporate workers that you have to help.

The next $$$q$$$ lines will contain one integer $$$N_{i}$$$ ($$$1 \leq i \leq q$$$ and $$$1 \leq N_{i} \leq 10^{18}$$$), representing the position of worker $$$i$$$'s home.

You must print $$$q$$$ lines. On every line $$$i$$$, output two integers: the minimum number of moves that the corporate worker $$$i$$$ has to make and the different ways in which he can take a minimum number of moves.

6
7
5
3
10
9
4

3 1
3 2
1 1
3 1
2 1
2 1