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.