SQREASY - Find the minimum no of squares

no tags 

Little Johny is a very playful kid and often he thinks about petty problems he comes across. One day he had a chocolate bar with him. He can eat a chocolate bar if and only if it is in the shape of a square whose edge is a multiple of  unit length .Little Johny eats atmost one piece of chocolate everyday. He wondered what is maximum number of days he can keep eating the given chocolate bar of  length L and width W. We all know that the answer is L*W if he eats 1*1 chocolate bar a day but Little Johny being a very greedy kid wants to finish the chocolate bar as soon as possible .Help him by finding the minimum number of days within which he can finish the chocolate bar.

Input

Input wil start with an integer T (the number of test cases) followed by T lines 

each line will contain two integers L and W (L and W are between 1 and 10^7 inclusively)

note: width can also be greater than hieght

Output

For each test case output the answer in a new line

Example

Input:
3
1 1
8 5
9 4

 Output:
1
5
6




Limits :

  1<=T<=1000
1<=L,W<=10000000


Added by:Ranjith Mudalaiyar
Date:2012-05-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem