Appro is the coach of Indian Women's Hockey team. She is currently training two teams Team A and Team B for the 2018 Women's Hockey World Cup to be held in London,England.

Team A consists of M players and B consists of N players.

To enhance the training she wants to divide them into groups of K players with every group being composed of people of only one of the original two teams.

Appro wants to know what is the maximum k for which this is possible?

Input:

The first line of input contains single integer T denoting the number of test cases.

Each line of test case contains 2 space separated integers M and N as specified in the problem.

Output:

For each test case, output the maximum value of K.

Constraints:

Subtask 1: \(30\) Points

\( 1\le T \le 100 \)

\( 1\le M,N \le 10^5 \)

Subtask 2: \(30\) Points

\( 1\le T \le 1000 \)

\( 1\le M, N \le 10^{9} \)

Subtask 3: \(40\) Points

\( 1\le T \le 10^5 \)

\( 1\le M, N \le 10^{18} \)