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 seperated 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 (seperated 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
aman9598: 2018-05-30 15:53:35

its my 50th

rishapverma100: 2018-01-23 15:40:03

just find the lcm then divide lcm by a and b...x and y will be respective values....AC in one go...

vkash: 2018-01-03 11:24:07

AC in one Go...!!

gourav_123: 2017-12-09 18:50:13

dont read comments....

moder_gabbar07: 2017-12-03 17:51:45

just solve eq for x and y.
find gcd of A and B.
Divide x and y with gcd.
boooooom. You got your answer ;)

nadstratosfer: 2017-12-02 03:23:07

Print minimum values of (x,y) not value of x&y, and not minimum value of x followed by matching y. Print each result on a separate line, don't insert additional newlines like comments suggest. Crap statement and crap judge: if a < b print the bigger value first else WA. WTF!

him_novice: 2017-09-05 05:15:37

Easiest question... Don't forget to print new line. Costed me one WA

secrets_inside: 2017-08-20 16:39:14

i used
a/=gcd(a,b);
b/=gcd(a,b);
n resulted 1 WA..:(

raichu7: 2017-07-30 03:45:42

AC in one go :)

one_mole: 2017-06-29 14:40:59

Last edit: 2017-06-29 14:41:55

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