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.

数字拆分

算法标签

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 位有符号整数范围内。