Problem E
Chinese Remainder Theorem (non-relatively prime moduli)

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$ .

Output

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

Sample Input 1	Sample Output 1
3 10000 23000 9000 23000 10000 23000 10000 23000 1234 2000 746 2002	no solution 10000 23000 489234 2002000

Hide

Please log in to submit a solution to this problem

Log in

CPU Time limit1 second

Memory limit1024 MB

?

DifficultyNot Available

LinksStatistics

DownloadsSample data files

Source & LicensePer AustrinKTH CSC Popup 2005

You haven't made any submissions on this problem yet.

Editor:

Problem EChinese Remainder Theorem (non-relatively prime moduli)

Input

Output

Problem E
Chinese Remainder Theorem (non-relatively prime moduli)