演算法(Algorithm)這個說法，第一次出現的地方，就是在”歐幾里德演算法” (Euclid’s algorithm)，而這個演算法就是我們所熟悉的輾轉相除法，用來求兩數的最大公因數。

我們現在有一個關於最大公因數的定理︰

給定正整數 m, n

方程式 am + bn = d 中

使得a, b有整數解的所有d之中，最大的那一個就是m, n的最大公因數

其中 (a, b) = 1

問題︰

給定正整數 m, n

am + bn = d 求 a, b, d

其中 d為m, n之最大公因數，且| a | + | b |為最小

輸入檔說明

輸入檔先給定一個正整數N，表示有N組輸入。接下來的N行，每行為一組測試資料，包含兩個用空格格開的數字 m, n。(1 £ m, n £ 65535)

輸出檔說明

對於每組m, n，輸出一行結果，包含用空白格開的三個數字 a, b, d。其中 -65536 £ a, b £ 65535，1 £ d £ 65535。