代码：

#include<bits/stdc++.h>
using namespace std;
int q,n,m,mins;
void dfs(int sum,int k,int s){
	if(s>=mins) return;
	if(sum==0){
		mins=s;
		return;
	}
	int p=sqrt(sum);
	for(int i=min(k,p);i>=1;i--) dfs(sum-i*i,i,s+1);
} 
int main(){
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&n,&m);
		mins=1e9;
		dfs(n,m,0);
		printf("%d\n",mins);
	}
	return 0;
}