/*
Problem description
用边长小于N的正方形方砖（注意，不要求所有的方砖大小相同，请看样例说明）不重叠地铺满N*N的正方形房间，最少要几块方砖。
Input
第一行是一个整数T,表示测试数据的组数,接下来的T 行，每一行是一个N(2<=N<=100)
Output
对于每一组测试数据输出一行，为最少需要的块数。
Sample Input
245
Sample Output
48
*/
#include <iostream>
using namespace std;
int GetNum(int m,int n)
{
int a=0;
if (n==0)
{
return 0;
}
a += m/n;
a += GetNum(n,m%n);
return a;
}
int main()
{
int T,N,temp,sum = 0,k=0;
//freopen("10086.txt","r",stdin);
cin>>T;
int *pRes = new int[T];
while (k<T)
{
cin>>N;
if (N%2==0)
{
pRes[k]=4;
k++;
continue;
}
if (N%3==0)
{
pRes[k]=6;
k++;
continue;
}
sum = N*N;
for (int i=N/2+1;i<N;i++)
{
temp = 0;
temp += GetNum(N,i);
temp += GetNum(N,N-i);
if (sum > temp)
sum = temp;
}
pRes[k]=sum;
k++;
}
责任编辑：cyth
