ENIGMATH - PLAY WITH MATH


You would have been fed up with competitive programming questions so far, now it is time to solve little math.

Assume you have a equation A × x - B × y = 0

For a given value of A and B, find the minimum positive integer value of x and y that satisfies this equation.

Input

First line contains T, number of test cases 0 ≤ T ≤1000 followed by T lines.

First line of each test case contains two space separated integers A and B. 1 ≤ A, B ≤1 000 000 000.

Output

For each test case, output a single line containing two integers x and y (separated by a single space).

Example

Input:
1
2 3

Output:
3 2

Note:

  • Brute force won't pass the given constraint.
  • Negative number cases are avoided to make the problem easy.

hide comments
newbie: 2015-10-21 13:25:20

got ac in first attempt
rightly said easy if u get d logic..

sri: 2015-09-03 17:38:48

Nice one! if u get the logic,then it is simple

Bozidar: 2015-04-22 21:41:26

Easy one. Green in first go.

Sue: 2015-02-28 16:46:45

It's such an easy game :))

Adnan Oquaish: 2015-01-25 18:08:28

Nice !! Related Question is Crucial Equations (pc:CEQU).


Added by:B.R.ARVIND
Date:2013-09-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64