Extended Euclidean Algorithm

You have just been taught about linear equations and about GCD(Greatest Common Divisor). So, you are given an equation AX + BY = C where A and B are two integers that you are given and D is the GCD or greatest common divisors of A and B.

So, you have to find out 2 integers x and y such that the above equation is satisfied for C = D, |X+Y| is minimum. If there are multiple such pairs, return the one where X is maximum.

Example:-

A = 2
B = 4
The answer should be D = 2 [gcd of (2,4)] and X = 1  and Y = 0 (|X+Y|=1 is the minimum possible value that can be obtained here).

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of every test case contains two integers ‘A’ and ‘B’ denoting the 2 coefficients.

Output Format :

For each test case, print three integers ‘D’, ‘X’, and ‘Y’ where ‘D’ is the gcd of ‘A’ and ‘B’ and ‘X’ and ‘Y’ are the two coefficients that satisfy the equation AX + BY = D.

The output of each test case should be printed in a separate line.

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.    

Constraints :

1 <= T <= 10
1 <= A <= 10^9
1 <= B <= 10^9

Time Limit = 1 sec