Start

2019-03-18 13:00 UTC

Kattis Set 09

End

2019-03-25 09:29 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -246 days 10:18:19

Time elapsed

164:29:59

Time remaining

0:00:00

Problem B
Chinese Remainder

Input

The first line of input consists of an integers $T$ where $1 \leq T \leq 1000$, the number of test cases. Then follow $T$ lines, each containing four integers $a$, $n$, $b$, $m$ satisfying $1 \leq n, m \leq 10^9$, $0 \leq a < n$, $0 \leq b < m$. Also, you may assume $\mbox{gcd}(n, m) = 1$.

Output

For each test case, output two integers $x$, $K$, where $K = nm$ and $0 \leq x < K$, giving the solution $x \pmod K$ to the equations $x = a \pmod n, x = b \pmod m$.

Sample Input 1 Sample Output 1
2
1 2 2 3
151 783 57 278
5 6
31471 217674