Common Fraction

A common fraction, also called a simple fraction, is a rational number written as $a/b$, where the integers $a$ and $b$ are the numerator and the denominator. The denominator cannot be zero.

Dividing the numerator and the denominator by the same non-zero number gives a fraction of equal value. That step is called reducing the fraction. A fraction whose numerator and denominator are coprime, meaning the only positive integer that divides both of them is 1, is in lowest terms. For example, $3/9$ is not in lowest terms because 3 and 9 are both divisible by 3. On the other hand, $3/8$ is in lowest terms, since the only positive integer that divides both 3 and 8 is 1.

Write a program that reduces the given fractions to lowest terms.

The first line contains the number of fractions $n$ ($1 \le n \le 10^4$).

Each of the next $n$ lines contains the numerator $a$ and the denominator $b$ of one fraction, separated by a space ($1 \le a \le 10^6$, $1 \le b \le 10^6$).

For each fraction, in the order it was given, print its lowest terms on one line. Separate the numerator and the denominator with a single space.