FUCT_FOR_REFRAC - Reduced fraction

reduced fraction

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

Added by:khanhvh
Date:2018-07-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:FPTU Can Tho

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.