You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明同学探索到一个古老的数学遗迹，在遗迹的深处发现了若干到道神秘的谜题。谜题中给出了整数 $n$ 和 $k$ ，并有如下提示：“在这个神秘的地方，存在着一类特殊的数字，它们的形式为 $3^m$（$m$ 是非负整数）。现在需要判断能否通过恰好 $k$ 个这样的特殊数字相加，得到整数 $n$ 。

换言之，是否存在一个非负整数序列 $\{a_k\}$，使得 $n = 3^{a_1} + 3^{a_2} + ... + 3^{a_k}$。

不出意外的，小明同学又把这个任务交给你了。

输入格式

输入的第一行包含一个正整数 $T$，表示谜题的个数。

接下来 $T$ 行，每行两个整数 $n,k$，表示一道谜题中的信息。

输出格式

输出共 $T$ 行。对于每一道谜题，如果可以则输出 Yes，否则输出 No。

4
5 3
17 2
163 79
1000000000000000000 1000000000000000000

Yes
No
Yes
Yes

样例 1 解释

对于第一个测试案例，$5 = 3^1 + 3^0 + 3^0$，因此满足了相关条件。

对于第二个测试案例，没有非负整数序列 $a_1,a_2$ 使得 $17 = 3^{a_1} + 3^{a_2}$，因此不满足有关条件。

其余样例见下发文件。
split2.in
split2.ans

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 10, k \le 5$。
• 对于另 $30\%$ 的数据，保证 $n \le 1000,k \le 2$。
• 对于 $100\%$ 的数据，保证 $1 \le k \le n \le 1 \times 10^{9},1\le T\le1 \times 10^5$。