Cho ba số nguyên \(𝑎, 𝑏, 𝑐\), trong đó \(𝑎, 𝑏\) không đồng thời bằng 0, \(|𝑎|, |𝑏|, |𝑐| \le 10^9\). Xét phương trình:

\(𝑎.𝑥 + 𝑏.𝑦 = 𝑐\)

Yêu cầu: Tìm một nghiệm (\(𝑥, 𝑦\)) của phương trình trên, với \(𝑥, 𝑦\) là các số nguyên thỏa mãn \(|𝑥|, |𝑦| \le 10^{18}\)

Input

• Dòng 1 chứa số nguyên dương \(𝑇 \le 10^4\) là số bộ dữ liệu
• \(𝑇\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương \(𝑎, 𝑏, 𝑐 \le 10^9\) cách nhau bởi dấu cách ứng với một bộ dữ liệu

Output

• Ứng với mỗi bộ dữ liệu ghi ra hai nghiệm \(𝑥, 𝑦\) tìm được trên một dòng, nếu phương trình không có nghiệm thỏa mãn điều kiện đặt ra, ghi ra trên dòng đó duy nhất một số 0

Các số trên một dòng của input/output được/phải ghi cách nhau bởi dấu cách

Example

3
10 7 16
2 8 3
1 2 3

3 -2
0
1 1