题目描述

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

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

输入格式

输入的第一行包含一个正整数 $T$ $(1 \leq T \leq 1 \cdot 10^5)$，表示谜题的个数。

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

输出格式

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

样例

4
5 3
17 2
163 79
1000000000000000000 1000000000000000000

Yes
No
Yes
Yes

样例解释

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

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