# Hackerrank: Restaurant

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 1^{st} 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 2^{nd} 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