Double or Triple - Repovive Starter Round 6 | Repovive

19B. Double or Triple

1000 pts1s256 MB

You have an integer $s$ . Initially, $s=1$ .

In one operation, you may perform exactly one of the following:

replace $s$ with $2s$ ;
replace $s$ with $3s$ .

You are given $q$ independent queries. In the $i$ -th query, find the smallest integer that can be obtained as $s$ and is greater than or equal to $n_i$ .

Constraints

$1 \le q \le 1000$
$1 \le n_i \le 10^{18}$

Input

The first line contains the number of queries $q$ .

Each of the next $q$ lines contains one integer $n_i$ .

q

\left. \begin{array}{l} n_i \end{array} \right\} \times q

Output

For each query, output the smallest obtainable integer that is greater than or equal to $n_i$ .

\left. \begin{array}{l} ans_i \end{array} \right\} \times q

Samples

Input

Case 1

Case 2

Case 3

Case 4

Case 5

Explanation

Case 1

The initial value is already at least $1$ , so no operation is needed.

Case 2

Starting from $1$ , multiplying by $2$ and then by $3$ produces $6$ . The value $5$ cannot be produced.

Case 3

The value $12$ can be produced as $1 \times 3 \times 2 \times 2$ . Neither $10$ nor $11$ can be produced.

Case 4

The value $72$ can be produced as $1 \times 2 \times 2 \times 2 \times 3 \times 3$ , so a larger value is unnecessary.

Case 5

The value $108$ can be produced as $1 \times 2 \times 2 \times 3 \times 3 \times 3$ . None of the integers from $100$ through $107$ can be produced.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You have an integer $s$ . Initially, $s=1$ .

In one operation, you may perform exactly one of the following:

replace $s$ with $2s$ ;
replace $s$ with $3s$ .

You are given $q$ independent queries. In the $i$ -th query, find the smallest integer that can be obtained as $s$ and is greater than or equal to $n_i$ .

$1 \le q \le 1000$
$1 \le n_i \le 10^{18}$

The first line contains the number of queries $q$ .

Each of the next $q$ lines contains one integer $n_i$ .

q

\left. \begin{array}{l} n_i \end{array} \right\} \times q

For each query, output the smallest obtainable integer that is greater than or equal to $n_i$ .

\left. \begin{array}{l} ans_i \end{array} \right\} \times q

The initial value is already at least $1$ , so no operation is needed.

Starting from $1$ , multiplying by $2$ and then by $3$ produces $6$ . The value $5$ cannot be produced.

The value $12$ can be produced as $1 \times 3 \times 2 \times 2$ . Neither $10$ nor $11$ can be produced.

The value $72$ can be produced as $1 \times 2 \times 2 \times 2 \times 3 \times 3$ , so a larger value is unnecessary.

The value $108$ can be produced as $1 \times 2 \times 2 \times 3 \times 3 \times 3$ . None of the integers from $100$ through $107$ can be produced.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

19B. Double or Triple

Constraints

Input

Output

Samples

19B. Double or Triple

Constraints

Input

Output

Samples