{"problem":{"name":"Ternary Decomposition","description":{"content":"You are given integers $N$ and $K$. Is it possible to express $N$ as the sum of exactly $K$ numbers of the form $3^m$ ($m$ is a non-negative integer)? In other words, is there a sequence of non-negati","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc164_a"},"statements":[{"statement_type":"Markdown","content":"You are given integers $N$ and $K$. Is it possible to express $N$ as the sum of exactly $K$ numbers of the form $3^m$ ($m$ is a non-negative integer)? In other words, is there a sequence of non-negative integers $(m_1, m_2,\\ldots, m_K)$ such that:\n$N= 3^{m_1}+3^{m_2}+...+3^{m_K}$?\nYou are given $T$ test cases. Answer each of them.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^5$\n*   $1 \\leq K \\leq N \\leq 10^{18}$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$ \n$\\mathrm{case}_T$\n\nEach test case, $\\mathrm{case}_i (1\\leq i \\leq T)$, is in the following format:\n\n$N$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc164_a","tags":[],"sample_group":[["4\n5 3\n17 2\n163 79\n1000000000000000000 1000000000000000000","Yes\nNo\nYes\nYes\n\nFor the first test case, we have $5=3^1+3^0+3^0$, so the condition in question is satisfied.\nFor the second test case, there is no sequence of non-negative integers $(m_1, m_2)$ such that $17=3^{m_1}+3^{m_2}$, so the condition in question is not satisfied."]],"created_at":"2026-03-03 11:01:13"}}