扩展欧几里得2

题目描述

输入 $T$ ，一共 $T$ 组数据，每组三个数 $a, b, d$ ，输出 $ax+by=d$ 的非负整数解 $(x, y)$ 。如果无解，那么输出 $-1$ ，否则输出 $x$ 最小的解。

第一行一个数字 $T$ 。

接下来 $T$ 行，每行三个数字 $a, b, d$ 。

一共 $T$ 行，每行两个数，表示 $x, y$ 。

3
1 2 5
100 150 1000
3 2 1

1 2
1 6
-1

对于 $100\%$ 的数据，保证$1\leq T\leq 10^4, 1\leq a, b\leq 10^9, 1\leq d\leq 10^{18}$。