贡献名单

题目描述

给你两个正整数 $n,m$，求和为 $n$ 的不大于 $m^2$ 的完全平方数的最少数量，如果无解则输出 $-1$。

输入格式

本题有多组数据。

第一行，一个正整数 $Q$，代表数据组数。

接下来 $Q$ 行，每行两个整数 $n,m$。

输出格式

$Q$ 行，每行一个数，对应一组数据的答案。

样例 #1

样例输入 #1

4
3 1
179 11
507 13
841 19

样例输出 #1

3
3
3
4

提示

样例解释：

$3=1^2+1^2+1^2.$

$179=11^2+7^2+3^2.$

$507=13^2+13^2+13^2.$

$841=18^2+16^2+15^2+6^2.$

请注意，对于第 $4$ 组数据，$841=29^2$ 不是合法的方案，因为 $29^2>19^2$。

对于 $100\%$ 的数据，$1 \le Q \le 10^6$，$1 \le n \le 10^{18}$，$1 \le m \le 100$。

提示： 请注意输入输出的效率。