Counting Hairband Configurations

Tianyi created a hairband for the Fox Constellation with a long ribbon consisting of small squares in two colors: white and purple. When the ribbon is folded, the squares pair up in the following way: for every positive integer k, the square at position -k overlaps with the square at position k, while the square at position 0 remains alone. The overlapping colors produce a new color as follows:

• Two white squares produce white.
• A white and a purple square produce light purple.
• Two purple squares produce dark purple.

We encode the colors as numbers: white as 0, light purple as 1, and dark purple as 2. Reading the colors of the folded ribbon from position 0 (the least significant digit) upward produces a ternary number:

[ x = d_0 \times 3^0 + d_1 \times 3^1 + d_2 \times 3^2 + \cdots ]

Notice that for the cell at position 0, only 0 (if white) or 1 (if purple) is allowed, while for each pair (positions -k and k for k > 0) we have three possibilities:

• Both white \(\to 0\) (1 way)
• One purple and one white \(\to 1\) (2 ways)
• Both purple \(\to 2\) (1 way)

This establishes a one-to-one correspondence between a hairband's style and a subset of integers \(S\) where the weight of \(S\) is defined by

[ W(S) = \sum_{a \in S} 3^{|a|}. ]

Given a nonnegative integer \(x\), determine the number of subsets \(S\) (where every element is unique) such that \(W(S) = x\). Two subsets are considered different if there exists an integer \(k\) such that one of them contains \(k\) and the other does not.

Note: In the ternary representation of \(x\), the digit corresponding to \(3^0\) (position 0) can only be 0 or 1. For each digit corresponding to \(3^k\) for \(k \ge 1\), the allowed digits are 0, 1, and 2. The number of hairband configurations corresponding to a particular ternary digit is 1 for digit 0, 2 for digit 1 (except for position 0 where it is 1) and 1 for digit 2.

inputFormat

The first line contains a single integer \(T\) (1 \(\le\) \(T\) \(\le\) 10⁵), the number of test cases.

Each of the next \(T\) lines contains a nonnegative integer \(x\) (\(0 \le x \le 10^{18}\)).

outputFormat

For each test case, output a single integer: the number of subsets \(S\) such that \(W(S)=x\>.

sample

5
0
1
3
4
8

1
1
2
2
0

</p>