Extended Euclidean Algorithm

Problem Description

Read $T$, then $T$ test cases follow. Each case gives two numbers $a, b$; output the minimal non-negative integer solution $(x, y)$ to $a x - b y = \gcd(a, b)$.

Input Format

The first line contains one integer $T$.

Each of the next $T$ lines contains two numbers $a, b$.

Output Format

Output $T$ lines, each containing two numbers: $x$ and $y$.

Sample Input

2
1 2
100 150

Sample Output

1 0
2 1

Constraints

For $100\%$ of the test cases, $1 \le T \le 10^4$ and $1 \le a, b \le 10^9$.