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
ss_1007: 2022-06-06 21:56:15

don't ignore "output a single line containing two integers x and y"\n ;)

sk128: 2021-04-05 14:31:51

AC in one go !!

divya14072002: 2021-04-02 12:22:55

AC in one go!

vivek_prime: 2021-01-27 07:03:34

AC in one go , elementary maths : hcf, lcm

raghav9352: 2020-09-02 13:52:30

AC IN ONE GO!!

manish_thakur: 2020-03-18 11:18:45

Don't look for hints in comments, observe for some time , and you'll be good to go!

saketvajp_123: 2019-12-20 11:05:58

take input as 130 and 117 and then check ....
for two different output(117 & 130 || 9 & 10) it accepts the answer.
one we get using sqrt function and other by simple gcd.

swap99: 2019-03-26 08:44:59

EASY PEASY

silentknight16: 2019-02-19 18:00:07

AC in one go!!

ankitpriyarup: 2018-12-19 19:25:17

Took me 2 WA finally ;)


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