 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
Second qualification round completed
Tasks
Show one task per page / all tasks on one page
Time limit  2 seconds 

Memory limit  256 megabytes 
Least common multiple is a well known term in math, it is the smallest number that is divisible by any of the given numbers. The concept of least common multiple can be generalized to other objects in math, for example to fractions.
You are given two irreducible fractions. Find their least common multiple — the smallest positive irreducible fraction p / q such that the result of the division of p / q to any of the given fractions is integer.
Input format 
Input contains several test cases. The first line of input contains integer t — the number of test cases (1 ≤ t ≤ 50 000). Each test case is described as a single line that contains four positive integers a, b, c, d, that correspond to irreducible fractions a / b and c / d (1 ≤ a, b, c, d ≤ 10^{9}). It is guaranteed that a / b and c / d are both irreducible. 

Output format 
For each test case output one line. Print two integers: numerator and denominator of the fraction that is a least common multiple of the given a / b and c / d fractions. 
Examples 
Input data
2 9 5 12 5 1 10 3 100
Output data
36 5 3 10 
