PEG Judge - WC02 - A Nerd's Preparation

Woburn Challenge 2002

Problem 9: A Nerd's Preparation

The Head-Monkey is a brilliant tactician, and what's more, she is brilliant at having her troops prepared for battle. This time the battle is for all the proverbial marbles. The Head-Monkey addresses her legion and says: "My fellow monkeys, this battle is for all the marbles!", to which Tiny responds, "Umm, no offence, do we get marbles if we win, Sir?!" After this issue is dealt with, the Head-Monkey decides it's time for the monkeys to prepare themselves for battle. The Head-Monkey is quite a pacifist, and firmly believes in brains before brawn. Confident of the fact that no matter how difficult the final battle, her monkeys will end up victorious if their minds are sharp, she poses the following problem: Given two fractions a/b and c/d find the fraction m/n between a/b and c/d (i.e. a/b < m/n < c/d) that has the smallest denominator (i.e. n is minimum). If there is more than one such fraction, output the smallest one. The Head-Monkey has guaranteed the following constraints:

a < b; c < d; 0 < b,d < 1000; a/b < c/d
a and b will have no common factors
c and d will have no common factors

BONUS: For the truly nerdy monkeys, the Head-Monkey has agreed to give a bonus (i.e., this problem will count as 1.5 problems solved) if the problem is solved for larger constraints: namely, a, b, c and d up to 2×10⁹.

Input

The first line contains a single integer, T (0 ≤ T ≤ 50), indicating the number of test cases.
Each test case consists of a single line containing four integers separated by a space, namely a, b, c and d. (These correspond to a/b and c/d)