## Hackerrank - Restaurant Solution

Martha is interviewing at Subway. One of the rounds of the interview requires her to cut a bread of size 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 . lines follow. Each line contains two space separated integers and which denote length and breadth of the bread.

**Constraints**

**Output Format**

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 0**

```
2
2 2
6 9
```

**Sample Output 0**

```
1
6
```

**Explanation 0**

The 1^{st} testcase has a bread whose original dimensions are 2x2, the bread is uncut and is a square. Hence the answer is 1.

The 2^{nd} testcase has a bread of size 6x9. We can cut it into 54 squares of size 1x1, 6 of size 3x3. For other sizes we will have leftovers. Hence, the number of squares of maximum size that can be cut is 6.

### Solution in Python

```
import math
def best(x,y):
prod = x*y
for i in range(2,int(math.sqrt(prod))+1)[::-1]:
if not x%i and not y%i:
return x*y//i**2
else:
return prod
for _ in range(int(input())):
x,y = list(map(int,input().split()))
print(best(x,y))
```