Martha is interviewing at Subway. One of the rounds of the interview requires her to cut a bread of size \(l\times b\) into smaller identical pieces such that each piece is a square having maximum possible side length with no left over piece of bread.
Input Format
The first line contains an integer \(T\).\(T\) lines follow. Each line contains two space separated integers \(l\) and \(b\) which denote length and breadth of the bread.
Constraints
\(1\leq T\leq 1000\)
\(1\leq l, b\leq 1000\)
Output Format
\(T\) lines, each containing an integer that denotes the number of squares of maximum size, when the bread is cut as per the given condition.
Sample Input
2
2 2
6 9
Sample Output
1
6
Explanation
The 1st testcase has a bread whose original dimensions are \(2\times 2\), the bread is uncut and is a square. Hence the answer is 1.
The 2nd testcase has a bread of size \(6\times 9\). We can cut it into 54 squares of size \(1\times 1\), 6 of size \(3\times 3\). For other sizes we will have leftovers. Hence, the number of squares of maximum size that can be cut is 6.
Solution
The question asks on how large can a square piece be to fit into the original area without any remainder. When we take another example with a bread of size \(10\times 15\) it is clear that to be square the largest common factor we can find is 5 such that we can order \(2\times 3\) squares of size 5. This is everything needed to solve the problem:
\[\begin{array}{rl} R(l, b) =& \frac{l}{\gcd(l, b)}\cdot\frac{b}{\gcd(l, b)}\\ =& \frac{l\cdot b}{\gcd(l, b)^2} \end{array} \]
The function can be implemented straight ahead with Ruby:
def restaurant(l, b)
l * b / l.gcd(b)**2
end