Second qualification round completed

Tasks

Show one task per page / all tasks on one page

"B" Least Common Multiple
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 ≤ 109). 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
 

Send solution

Upload Maximal size is 256kb

Log in

VK Facebook

Forgot password?

Registration

The instruction for password recovery
has been sent to your email