Arun is Varun's maths teacher. He gives him a function $F(X)$, which is defined as follows :

1. If $X$ is a multiple of $2$, then $F(X)$ will be $F(\frac{X}{2})$.
2. If $X$ is a multiple of $3$, then $F(X)$ will be $F(\frac{X}{3})$.
3. If $X$ is a multiple of both $2$ and $3$, then $F(X)$ will be $F(\frac{X}{2})$ + $F(\frac{X}{3})$.
4. Else $F(X)$ will be equal to $X$.

Now, Arun gives him $Q$ queries and in each query, a value of $X$ is given. Varun's task is to solve for $F(X)$. Since there are many queries help Varun to pass this assignment.

Output can be large, return $F(X) \bmod 1000000007$.

Input format

First-line contains $Q$ - the number of queries.

Next $Q$ lines contain an integer $X$.

Output format

Print $Q$ lines each contain the value of $F(X)$.

Constraints

$1 \le Q \le 10^5 \\ 1 \le X \le 10^{18}$