Gazu is a bright kid fascinated by the concept of number line. He made a long number line (0 to infinity) in his backyard and decided to play “Jump on cherry”. He stood at zero of the number line and jumped X distance ahead. After he jumps he throws a red cherry Y distance ahead. Again he jumps X distance ahead and then he throws a new red cherry 2Y distance ahead, again he jumps X ahead and throws a new red cherry 3Y distance ahead. He repeats these steps until he jumps on a red cherry. Now he asks you to calculate the time after which he will jump on a cherry.
Assuming: he jumps after every 1 second, time elapsed in throwing a cherry is zero second, there was no cherry on the ground before the game and Gazu have infinite supply of cherries.

INPUT
first line contains number of testcases 0<t<100, next t lines contains two space separated integers corresponding to X and Y. 2<X,Y<2000

OUTPUT
t lines, each containing the time (in seconds) after Gazu will jump on a cherry for each testcase.

SAMPLE INPUT
1
4 2

SAMPLE OUTPUT
3

Explanation

X=4 and Y=2
See picture above in the problem statement.
Total number of jumps required to jump on a cherry x time elapsed in single jump= Total time
3 jumps x 1 second= 3 seconds

见题面

见题面