求助

正方形分割(cut)
问题描述：
给定一个长方形，把它分割成若干个正方形，求最少能分成几个？
输入格式：
第一行为正整数t(≤50)，表示数据组数；接下来t行，每行两个正整数a和b，表示长方形的长和宽，b<a<109。
输出格式：
对于每组数据，输出分割出正方形的最少数目。
输入样例	
2
10 7
100000000 1	
输出样例
6
100000000

#include<stdio.h>
#pragma GCC optimize(2)
void work(){
    int ans=1,a,b;
    scanf("%d%d",&a,&b);
    if(b>a){
    	int c=a;
		a=b,b=c;
	}
	if(!(a%b)){
		printf("%d\n",a/b);
		return ;
	}
	else{
		a%=b;
		if(a>b){
    		int c=a;
			a=b,b=c;
		}
		while(a&&b){
			ans+=b/a;
			b-=(b/a)*a;
			if(a>b){
    			int c=a;
				a=b,b=c;
			}
		}
	}
	printf("%d\n",ans);
	return ;
}
int main(){
    freopen("cut.in","r",stdin);
    freopen("cut.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--) work();
    return 0;
}

大样例输入
2
314 6563
23165 96231146
大样例输出
41
4253