Ozan is a fantastic person and loves the number 3 very much. Since he loves the number 3 very much, he gives the name fantastic number to the numbers can be constructed only with different powers of 3.

• 3 is a fantastic number. \(\mathbf{(3 = 3^{1})}\)
• 13 is a fantastic number. \(\mathbf{(13 = 3^{2}+3^{1}+3^{0})}\)
• 1 is a fantastic number. \(\mathbf{(1 = 3^{0})}\)
• 6 is not a fantastic number, because it can't be constructed using only different powers of 3. \(\mathbf{(6 = 3^{1}+3^{1} = 3^{1}+3^{0}+3^{0}+3^{0})}\)
• 26 is not a fantastic number. \(\mathbf{(26 = 3^{2}+3^{2}+3^{1}+3^{1}+3^{0}+3^{0})}\)
• 0 is not a fantastic number, becase it can't be written using any of the powers of 3.

Although Ozan loves fantastic numbers, he doesn't know how many are there. He wants your help to find how many fantastic numbers there are.

Ozan gives you \(\mathbf{n}\) many numbers and wants to know the number of fantastic numbers less than or equal to that number.

Input

The first line only consists of the number \(\mathbf{n}\).

Each of the next \(\mathbf{q}\) lines include an element of \(\mathbf{a_1, a_2, ... ,a_n}\).

Batch #1:

• \(1 \leq \mathbf{n} \leq 100\)
• \(1 \leq \mathbf{a_i} \leq 10^{5}\)

Batch #2:

• \(1 \leq \mathbf{n} \leq 500\)
• \(1 \leq \mathbf{a_i} \leq 10^{18}\)

Output

In \(\mathbf{n}\) lines, print the number of fantastic numbers smaller than or equal to \(\mathbf{a_i}\) in the \(\mathbf{i}\)'th line.

Samples

Input:

3
2
5
12

Output:

1
3
6

Input:

1
100000

Output:

2047

Explanation

1. Input

• All the fantastic number to number 2 \(\mathbf{\{1 = 3^{0}\}}\).
• All the fantastic number to number 5 \(\mathbf{\{1 = 3^{0}, 3 = 3^{1}, 4 = (3^{1} + 3^{0}) \}}\).
• All the fantastic number to number 12 \(\mathbf{\{1 = 3^{0}, 3 = 3^{1}, 4 = (3^{1} + 3^{0}), 9 = 3^{2}, 10 = (3^{2} + 3^{0}), 12 = (3^{2} + 3^{1}\}}\).