背景

  「芳菲歇去何须恨，夏木阴阴正可人」

  和老 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}$。

对于不同的测试点，作如下约定：