Enter the numerator and denominator of a fraction. Reduce that fraction.

Input

The first line of the input consist of a single integer number t which determines the number of tests.

In each of next t lines will contain numerator and denominator of the fraction that separated by a space.

Constraints

• 0 < t ≤ 1 000

Output

For each test case print out the numerator and denominator of the reduced fraction that separated by a space. Separate your answers with a new line character.

Example

Input:
8
-8 16
1 9
8 10
-3 0
150 200
-9 -12
27 9
45 -50

Output:
-1 2
1 9
4 5
the denominator can not be zero
3 4
3 4
3
-9 10