# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* still_me

*the_hyp0cr1t3, rivalq*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

# PROBLEM:

Find the maximum number of people who can split N apples and M oranges equally.

# EXPLANATION:

Suppose there were k people. Then, for equal distribution, k must be a divisor of N *and* a divisor of M.

The largest such k is, by definition, \gcd(N, M); and this is the answer.

Finally, since N and M can be quite large, it’s necessary to compute \gcd(N, M) quickly. This can be done with the help of the Euclidean algorithm, or you can just use inbuilt functions corresponding to your language (`std::gcd`

in C++, `math.gcd`

in Python, and so on).

# TIME COMPLEXITY:

\mathcal{O}(\log\min(a, b)) per testcase.

# CODE:

## Code (Python)

```
from math import gcd
for _ in range(int(input())):
n, m = map(int, input().split())
print(gcd(n, m))
```