Least Common Multiple Solution

Page Contents

Least Common Multiple

Prepbuddy is very fond of solving maths problems. One day his teacher after taking a class on Least common multiple (LCM), gave him a question in which he was given two irreducible fractions and was asked to find their least common multiple — the smallest positive irreducible fraction P/QP/Q such that the result of the division of P/QP/Q to any of the given fractions is an integer.

Actually, Prepbuddy thought that he knows the concept very well but now he is having difficulty in coming up with the solution. Help him to come up with a solution

He knew that LCM is the smallest number that is divisible by all the given numbers whose LCM we are trying to find. The concept of least common multiple can be generalized to other objects in math, for example to fractions.

Input Format

The first line of input contains an integer TT denoting the number of test cases. The first line of each test case is described as a single line that contains four positive integers AA, BB, CC, DD, that correspond to irreducible fractions A/BA/B and C/DC/D. It is guaranteed that A/BA/B and C/DC/D are both irreducible.

Output Format

For each test case print two integers numerator and denominator of the fraction that is a least common multiple of the given A/BA/B and C/DC/D fractions.

Constraints

1≤T≤5∗1041≤T≤5∗104 1≤A,B,C,D≤1091≤A,B,C,D≤109

Time Limit

2 second

Example

Sample Input

2 9 5 12 5 1 10 3 100

Sample Output

36 5 3 10

Note : Please click on 1 or 2 ads to help us run this site and encourages us to provide you the solutions.