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

19B. Double or Triple

Constraints

Input

Output

Samples

19B. Double or Triple

Constraints

Input

Output

Samples