By Victor Marcilio Peixoto, UNIVASF Brazil
In an attempt to stop Super Buu, Goten and Trunks entered the Time Room to train. Time passes faster inside this room (1 second outside the room might be equivalent to seconds, minutes, hours or even days inside the room). Goten and Trunks need X seconds to finish training, however Super Buu has become impatient and ordered Mr. Picollo to take him to his opponents immediately.
Mr. Picollo used his telephatic powers to alert the boys (who had done nothing so far but playing around the room) and they started training immediately.
Mr. Picollo did his best to delay the path to the Time Room, taking Y to do so.
Let K be the number of seconds that passes inside the room during 1 second outside it. Find the smallest value for K that'll give the boys enough time to finish their training before Super Buu's arrival. Consider that the boys have plenty Senzu Beans therefore they will never need to stop training to rest and the training ends when Super Buu get through the entrance door.
The first input line contains an integer T (1 ≤ T ≤ 100), the number of test cases. The following T lines contain 2 integers each: X (1 ≤ X ≤ 1015) e Y (1 ≤ Y ≤ 105), the time needed to finish the training and Super Buu's path time, respectively.
For each test case output a single line containing the integer K.
|Input Sample||Output Sample|