数字拆分

算法标签

Level2, 数学2, GESP3级

题目背景

小明是一位热衷于探索古老数学遗迹的探险家。他发现了一些神秘的谜题，需要你来帮助他解决。

题目描述

在一个古老的遗迹中，给定整数 $n$ 和 $k$，需要判断能否通过恰好选择 $k$ 个形如 $3^m$（$m$ 为非负整数）的特殊数字相加得到 $n$。

换言之，是否存在非负整数序列 $\{a_1, a_2, \dots, a_k\}$，使得

输入格式

第一行包含一个正整数 $T$，表示谜题的个数。
接下来 $T$ 行，每行包含两个整数 $n$ 和 $k$。

输出格式

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

样例

4
5 3
17 2
5 2
1000000000000000000 1000000000000000000

Yes
No
Yes
Yes

样例解释

样例一：$5 = 3^1 + 3^1 + 3^0$，故输出 Yes。
样例二：无法用两个 $3^m$ 的和表示 17，故输出 No。

数据范围

• 对于 30% 的数据，保证 $n \le 10,\ k \le 5$。
• 对于 30% 的数据，保证 $n \le 1000,\ k \le 2$。
• 对于 100% 的数据，保证 $1 \le k \le 10^9,\ 1 \le T \le 10^5,\ n$ 在 64 位有符号整数范围内。