Description

Recently Doctor Wang has discovered two new kinds of bacteria and named them BT_U and BT_V. BT_U and BT_V are quite special, They can only live with the help of each other. Doctor Wang did several experiments on BT_U and BT_V, here’re the results:

Put 100 BT_Us and 80 BT_Vs together, one minute later, there are 20 BT_Us and 80 BT_Vs, one minute later again, there are 20 BT_Us and 60 BT_Vs, then 20 BT_Us and 40 BT_Vs, then 20 BT_Us and 20 BT_Vs, then these 20 BT_Us and 20 BT_Vs keep alive.

Puts 3 BT_Us and 5 BT_Vs together, one minute later, there are 3 BT_Us and 2 BT_Vs, one more minute later there are 1 BT_U and 2 BT_Vs, then 1 BT_U and 1 BT_V, and this 1 BT_U and 1 BT_V keep alive.

According to the results above, Doctor Wang has reached a conclusion that when putting x BT_Us and y BT_Vs together, if x=y then they keep alive. if xy then y BT_Us would die in one minute. Doctor Wang has made a program to determine how many BT_Us and BT_Vs survive when putting x BT_Us and y BT_Vs together. Program is as follow:

//===========================

// Research for BT_U and BT_V

//===========================

include"iostream"

using namespace std;

//---------------------------

int main(){

for(int x,y; cin>>x>>y; ){

while(x!=y)

x>y ? x-=y : y-=x;

cout<<x<<”\n”;

}

}//==========================

But this program is quite inefficient. Doctor Wang needs your help to improve it.

Input

There’re multiple cases. For each case there’s one line containing two integers for x and y(0<x,y<1000000000).

Output

For each case output the result in a single line.

Sample

Input

100 80
3 5

Output

20
1

Source: qn