好好好数

题号：NC276193
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\,\,\,\,\,\,\,\,\,$ 在上周的周赛 $\textsf {Round 57}$ 中，双好数的构造题非常有趣，于是，在这周的周赛中，好数又回来了！但是其实这两题并没有什么关系，还是重新看看题吧！

$\,\,\,\,\,\,\,\,\,$ 小苯有一个数字 $n$ ，他定义 $\texttt{k-}$ 好数为：可以表示为若干个不同的 $k$ 的整数次幂之和的数字。

$\,\,\,\,\,\,\,\,\,$ 例如： $30 = 3^3+3^1$ ，因此 $30$ 是一个 $\texttt{3-}$ 好数，而 $2$ 不是一个 $\texttt{3-}$ 好数（虽然有： $2=3^0+3^0$ ，但好数要求次幂数字不同）。
$\,\,\,\,\,\,\,\,\,$ 小苯有一个整数 $n$ ，他想知道 $n$ 最少可以被表示成几个 $\texttt{k-}$ 好数的和，请你帮帮他吧。

输入描述:

 每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

在一行上输入两个整数  ，表示小苯的数字  、 好数的  。

输出描述:

在一行上输出一个整数，代表最少可以将  分解成  好数的个数。

示例1

输入

复制

2
60 3
114 514

输出

复制

2
114

说明

对于第一组测试数据， 是  好数，而  ，因此可以分解为两个  好数，可以证明不存在更优的分解方式。