「GLR-R4」立夏

  「芳菲歇去何须恨，夏木阴阴正可人」 ---   和老 V 说好的赛后团建终于举行啦！   难得和学弟学妹们在一起，天依和阿绫自然不会错过这次良好的机会，更不会放过早就想 rua 的狐狸座的耳朵！   “那个……天依……”   天依和腿上的狐狸座同时歪过头看向某个叫阿绫的醋坛子。   “绫姐绫姐，疼！”   于是在天依给小狐狸扎头发的时候，小狐狸的耳朵已经被揉蔫啦！ ---   **立夏** 「三步并两步　就发现　如期而至的透明夏日章节」

  **本题提供简要题意。**   天依给狐狸座准备的纱质发绳由**白色**和**紫色**的小格子组成，相同大小的小格子连成了一条足够长的带子。我们不妨把天依的手正捏着的位置标为第 $0$ 格，向右依次是第 $1$ 格、第 $2$ 格，等等；向左依次是第 $-1$ 格，第 $-2$ 格，等等；天依将发绳对折起来，此时第 $-1$ 格将于第 $1$ 格重合，第 $-2$ 格将于第 $2$ 格重合……第 $-k$ 格将与第 $k$ 格重合（$k$ 为正整数）。**特别地**，我们认为第 $0$ 格保持原样，没有和其他格子重合，也没有和自己重合。   由于发绳是半透光的，所以对折起来的发绳上的格子将可能出现三种颜色：**白色**、**浅紫色**和**深紫色**。两个白色的格子重合呈现白色，一个紫色和一个白色的格子重合呈现浅紫色，两个紫色的格子重合呈现深紫色。**特别地**，若第 $0$ 格原来为白色，则折叠后也为白色，否则第 $0$ 格原来为紫色，则折叠后为浅紫色。   如果把白色记作 $0$，浅紫色记作 $1$，深紫色记作 $2$，以折叠后的第 $0$ 格作为最低位，依次将每个格子颜色对应的数字记录下来，我们将得到一个长长的三进制数整数，记为 $x$。现在，天依告诉你了 $x$ 的值，你能算出**对折之前的发绳**有多少种不同的样式吗？称两条发绳颜色不同，当且仅当存在一个整数 $k$，使得两条发绳的第 $k$ 格上的颜色不相同。   发绳款式丰富多样，你需要对 $T$ 个 $x$ 分别求出答案。 ### 简要题意   对于一个包含整数的集合 $S$，定义其权值为 $\sum_{a\in S}3^{|a|}$（即，枚举 $S$ 的元素 $a$，计算 $3^{|a|}$ 并求和）。给出非负整数 $x$，计算有多少个集合的权值为 $x$。注意集合不能包含重复元素。

第一行一个整数 $T$，表示你需要分别处理的数据组数。 接下来 $T$ 行，每行一个整数 $x$，表示对折后发绳颜色所对应的三进制数。注意 $x$ 是以十进制输入的。

输出 $T$ 行，第 $i$ 行一个整数，表示给出的第 $i$ 个 $x$ 对应的方案数。

2
12
2

4
0

#### 样例 #1 解释 $x=12$ 时，有四种可能的发绳样式，它们的紫色格子位置分别是 $\{-1,-2\}$，$\{-1,2\}$，$\{1,-2\}$，$\{1,2\}$。 $x=2$ 时，不存在任何满足条件的发绳样式，此时输出 $0$ 即可。 ### 数据规模与约定 对于 $100\%$ 的数据，$1 \leq T \leq 10^5, 0 \leq x \leq 10^{18}$。 对于不同的测试点，作如下约定： | 测试点编号 | $x$ | 特殊性质 | | :--------: | :--------------: | :--------: | | $1\sim3$ | $\leq 3^{10}$ | 无 | | $4$ | $\leq 10^{18}$ | $x \bmod 3 = 1$ | | $5$ | $\leq 10^{18}$ | $x \bmod 3=2$ | | $6$ | $\leq 10^{18}$ | $x \bmod 3 =0$ | | $7\sim10$ | $\leq 10^{18}$ | 无 |