Background

  "When the spring flowers fade away, there is no need to regret; the summer trees are lush and pleasantly shaded."

  The post-contest meetup that was agreed on with Old V is finally happening!

  It is rare to be together with the juniors, so Tianyi and Ayling naturally will not miss this good chance, and they definitely will not let go of the chance to rua the fox-eared Constellation’s ears that they have wanted to for a long time!

  "Um... Tianyi..."

  Tianyi and the fox-eared Constellation on her lap tilt their heads at the same time and look at someone called Ayling, a jealous "vinegar jar".

  "Sister Ayling, sister Ayling, it hurts!"

  So when Tianyi is tying the little fox’s hair, the little fox’s ears have already been揉蔫啦 (rou nian la, kneaded until limp)!

  Start of Summer  "In two or three quick steps, you discover the transparent summer chapter arriving right on time."

Problem Description

  This problem provides a brief statement.

  The gauze hairband that Tianyi prepared for the fox-eared Constellation is made of white and purple small squares. Small squares of the same size are connected into a long enough strip. Let the position that Tianyi is pinching with her hand be square $0$. To the right are square $1$, square $2$, and so on; to the left are square $-1$, square $-2$, and so on. Tianyi folds the hairband in half. Then square $-1$ overlaps with square $1$, square $-2$ overlaps with square $2$, ... square $-k$ overlaps with square $k$ ($k$ is a positive integer). In particular, we consider square $0$ to remain as it is: it does not overlap with any other square, and it does not overlap with itself.

  Because the hairband is semi-transparent, after folding, the squares on the folded hairband may show three colors: white, light purple, and dark purple. Two white squares overlapping appear white; one purple and one white overlapping appear light purple; two purple squares overlapping appear dark purple. In particular, if square $0$ was originally white, then it is still white after folding; otherwise, if square $0$ was originally purple, then it becomes light purple after folding.

  If we record white as $0$, light purple as $1$, and dark purple as $2$, and take folded square $0$ as the least significant digit, then write down the digit corresponding to each square’s color in order, we obtain a long ternary integer, denoted as $x$. Now, Tianyi tells you the value of $x$. Can you compute how many different styles the hairband before folding could have? We say two hairbands have different colors if and only if there exists an integer $k$ such that the color of square $k$ on the two hairbands is different.

  There are many possible hairband styles, and you need to answer the result for each of $T$ given values of $x$.

Brief statement

  For a set $S$ that contains integers, define its weight as $\sum_{a\in S}3^{|a|}$ (that is, enumerate each element $a$ in $S$, compute $3^{|a|}$, and sum them up). Given a non-negative integer $x$, compute how many sets have weight equal to $x$. Note that a set cannot contain duplicate elements.

Input Format

The first line contains an integer $T$, indicating the number of test cases you need to process.

The next $T$ lines each contain an integer $x$, representing the ternary number corresponding to the colors of the hairband after folding. Note that $x$ is given in decimal.

Output Format

Output $T$ lines. The $i$-th line contains one integer, representing the number of valid ways for the $i$-th given $x$.

2
12
2

4
0

Hint

Explanation for Sample #1

When $x=12$, there are four possible hairband styles. The positions of the purple squares are $\{-1,-2\}$, $\{-1,2\}$, $\{1,-2\}$, $\{1,2\}$, respectively.

When $x=2$, there is no hairband style that satisfies the condition, so output $0$.

Constraints

For $100\%$ of the testdata, $1 \leq T \leq 10^5, 0 \leq x \leq 10^{18}$.

For different test points, the following constraints apply:

Translated by ChatGPT 5