该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在提瓦特大陆的命之座研究中 , 旅行者发现了「元素共鸣矩阵」的规则：

若角色 $\rm e$ 属性的能量值 $\rm N$ 能表示为若干个不同的 $\rm e$ 的非负幂次之和 , 则称 $\rm N$ 为该角色的命之座能量体

形式化的说 :$\rm N = e^{k_1} + e^{k_2} + \dots + e^{k_m}$ , 其中 $\rm k_1, k_2, \dots, k_m$ 为互不相同的非负整数

如:

• 钟离($\rm e=3$)：元素爆发「地心」的能量 $30$ 可表示为 $3^3 + 3^1$ (指数 $3$ 和 $1$ 不同) , 因此 $30$ 是钟离的命之座能量体

• 温迪($\rm e=2$)：元素战技的能量 $11$ 可表示为 $2^3 + 2^1 + 2^0$(指数 $3, 1, 0$ 互不相同) , 故 $11$ 是温迪的命之座能量体

• 雷电将军 ($\rm e=3$)：能量 $2$ 若表示为 $3^0 + 3^0$ (指数重复为 $0$) 则不满足定义 , 因此不是命之座能量体

冒险家协会委托旅行者优化能量合成方案：给定总能量值 $\rm S$ 和角色的元素属性 $\rm e$ , 需计算 $\rm S$ 最少可分解为该角色的命之座能量体的个数

输入格式

第一行输入一个整数 $\rm T$ , 表示 $\rm T$ 个任务

每个任务输入一行两个空格分隔的整数 $\rm S,e$

输出格式

对于每组任务输出一行一个整数 , 即 $\rm S$ 最少可分解为该角色命之座能量体的个数

若无法分解则输出一行 $\rm NO$

5
1 1
60 3
1145 141
919 81
3450234 39

1
2
17
28
21

样例1解释

对于第二组询问 $60 = \textcolor{#d00}{30} + \textcolor{blue}{30} = \textcolor{#d00}{3^3+3^1} + \textcolor{blue}{3^3+3^1}$

4
763 1753
901741822 873775403
838853502252068282 618602077216111542
239289379070278004 218606282174081543

763
27966419
220251425035956740
20683096896196461

数据规模

对于 $12\%$ 的数据 $\rm 1 \leq T,S,e \leq 10$

对于 $48\%$ 的数据 $\rm 1 \leq T \leq 100 , 1 \leq S,e \leq 2000$

对于 $68\%$ 的数据 $\rm 1 \leq T \leq 1000 , 1 \leq S,e \leq 10^9$

对于 $100\%$ 的数据 $\rm 1 \leq T \leq 10^5 , 1 \leq S,e \leq 10^{18}$