#include<iostream>
#include<vector>
using namespace std;
int f[62][62],T;
struct{
	int x1,y1;
	int x2,y2;
}minF[62][62];//记录某个长方形的最小正方形切割数是由哪两个长方形得来的
//dp
inline int F(int n,int m){
	if(f[n][m])return f[n][m];
	if(n==m)return f[n][m]=1;//边界条件
	f[n][m]=114514;//......就是设一个很大的值
	for(int i=1;i<n;i++)
		if(F(i,m)+F(n-i,m)<f[n][m]){
			f[n][m]=F(i,m)+F(n-i,m);//转移
			minF[n][m]={i,m,n-i,m};//记录
		}
	for(int i=1;i<m;i++)
		if(F(n,i)+F(n,m-i)<f[n][m]){
			f[n][m]=F(n,i)+F(n,m-i);
			minF[n][m]={n,i,n,m-i};
		}
	return f[n][m];
}
struct Square{
	int x,y,l;
};//一个正方形
vector<Square> ans;//记录答案
void sol(int n,int m,int x,int y){
	if(n==m){
		ans.push_back({x,y,n});
		return;//边界条件
	}
	auto k=minF[n][m];//方便
	if(n==1){
		for(int i=0;i<m;i++)
			ans.push_back({x,y+i,1});
		return;
	}
	if(m==1){
		for(int i=0;i<n;i++)
			ans.push_back({x+i,y,1});
		return;
	}//两个微不足道的剪枝
	if(k.x1==k.x2&&k.y1==k.y2){
		sol(k.x1,k.y1,x,y);
		if(n<m)sol(k.x2,k.y2,x,y+k.y1);
		else sol(k.x2,k.y2,x+k.x1,y);
		return;
	}//如果由两个同样的长方形构成
	if(k.x1==k.x2){
		sol(k.x1,k.y1,x,y);
		sol(k.x2,k.y2,x,y+k.y1);
	}//如果是由两个长方形横向拼接
	if(k.y1==k.y2){
		sol(k.x1,k.y1,x,y);
		sol(k.x2,k.y2,x+k.x1,y);
	}//竖向拼接
}
int main(){
	cin>>T;
	for(int i=1;i<=60;i++)
		for(int j=1;j<=60;j++)
			F(i,j);//dp
	while(T--){
		int n,m;cin>>n>>m;
		cout<<f[n][m]<<endl;//先输出答案
		ans.clear();
		sol(n,m,0,0);//求解
		for(auto i:ans)
			cout<<i.x<<" "<<i.y<<" "<<i.l<<endl;//输出
	}
}

评测结果显示 (11x13) 的长方形只需要 6 个正方形，我的输出是 8 ，求助。