{"problem":{"name":"「GLR-R4」立夏","description":{"content":"  **本题提供简要题意。**   天依给狐狸座准备的纱质发绳由**白色**和**紫色**的小格子组成，相同大小的小格子连成了一条足够长的带子。我们不妨把天依的手正捏着的位置标为第 $0$ 格，向右依次是第 $1$ 格、第 $2$ 格，等等；向左依次是第 $-1$ 格，第 $-2$ 格，等等；天依将发绳对折起来，此时第 $-1$ 格将于第 $1$ 格重合，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9154"},"statements":[{"statement_type":"Markdown","content":"  **本题提供简要题意。**\n\n  天依给狐狸座准备的纱质发绳由**白色**和**紫色**的小格子组成，相同大小的小格子连成了一条足够长的带子。我们不妨把天依的手正捏着的位置标为第 $0$ 格，向右依次是第 $1$ 格、第 $2$ 格，等等；向左依次是第 $-1$ 格，第 $-2$ 格，等等；天依将发绳对折起来，此时第 $-1$ 格将于第 $1$ 格重合，第 $-2$ 格将于第 $2$ 格重合……第 $-k$ 格将与第 $k$ 格重合（$k$ 为正整数）。**特别地**，我们认为第 $0$ 格保持原样，没有和其他格子重合，也没有和自己重合。\n\n  由于发绳是半透光的，所以对折起来的发绳上的格子将可能出现三种颜色：**白色**、**浅紫色**和**深紫色**。两个白色的格子重合呈现白色，一个紫色和一个白色的格子重合呈现浅紫色，两个紫色的格子重合呈现深紫色。**特别地**，若第 $0$ 格原来为白色，则折叠后也为白色，否则第 $0$ 格原来为紫色，则折叠后为浅紫色。\n\n  如果把白色记作 $0$，浅紫色记作 $1$，深紫色记作 $2$，以折叠后的第 $0$ 格作为最低位，依次将每个格子颜色对应的数字记录下来，我们将得到一个长长的三进制数整数，记为 $x$。现在，天依告诉你了 $x$ 的值，你能算出**对折之前的发绳**有多少种不同的样式吗？称两条发绳颜色不同，当且仅当存在一个整数 $k$，使得两条发绳的第 $k$ 格上的颜色不相同。\n\n  发绳款式丰富多样，你需要对 $T$ 个 $x$ 分别求出答案。\n\n### 简要题意\n\n  对于一个包含整数的集合 $S$，定义其权值为 $\\sum_{a\\in S}3^{|a|}$（即，枚举 $S$ 的元素 $a$，计算 $3^{|a|}$ 并求和）。给出非负整数 $x$，计算有多少个集合的权值为 $x$。注意集合不能包含重复元素。\n\n## Input\n\n第一行一个整数 $T$，表示你需要分别处理的数据组数。\n\n接下来 $T$ 行，每行一个整数 $x$，表示对折后发绳颜色所对应的三进制数。注意 $x$ 是以十进制输入的。\n\n## Output\n\n输出 $T$ 行，第 $i$ 行一个整数，表示给出的第 $i$ 个 $x$ 对应的方案数。\n\n[samples]\n\n## Background\n\n  「芳菲歇去何须恨，夏木阴阴正可人」\n\n---\n\n  和老 V 说好的赛后团建终于举行啦！\n\n  难得和学弟学妹们在一起，天依和阿绫自然不会错过这次良好的机会，更不会放过早就想 rua 的狐狸座的耳朵！\n\n  “那个……天依……”\n\n  天依和腿上的狐狸座同时歪过头看向某个叫阿绫的醋坛子。\n\n  “绫姐绫姐，疼！”\n\n  于是在天依给小狐狸扎头发的时候，小狐狸的耳朵已经被揉蔫啦！\n\n---\n\n  **立夏** 「三步并两步　就发现　如期而至的透明夏日章节」\n\n## Note\n\n#### 样例 #1 解释\n\n$x=12$ 时，有四种可能的发绳样式，它们的紫色格子位置分别是 $\\{-1,-2\\}$，$\\{-1,2\\}$，$\\{1,-2\\}$，$\\{1,2\\}$。\n\n$x=2$ 时，不存在任何满足条件的发绳样式，此时输出 $0$ 即可。\n\n### 数据规模与约定\n\n对于 $100\\%$ 的数据，$1 \\leq T \\leq 10^5, 0 \\leq x \\leq 10^{18}$。\n\n对于不同的测试点，作如下约定：\n\n| 测试点编号 |       $x$        | 特殊性质 |\n| :--------: | :--------------: | :--------: |\n|    $1\\sim3$     |      $\\leq 3^{10}$      |   无   |\n|    $4$     |  $\\leq 10^{18}$ |   $x \\bmod 3 = 1$    |\n|    $5$     |    $\\leq 10^{18}$     |  $x \\bmod 3=2$   |\n|    $6$     |   $\\leq 10^{18}$   |  $x \\bmod 3 =0$   |\n|    $7\\sim10$     |   $\\leq 10^{18}$   |  无  |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9154","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["2\n12\n2","4\n0"]],"created_at":"2026-03-03 11:09:25"}}