Our friend giraffe has been given a "mammoth" task.
Given 2 numbers A and B,
giraffe needs to represent it as an irreducible fraction, i.e. in P/Q form such that P and Q are Co-primes.

Help our dear friend Giraffe by printing the P+Q

examples :
1 : A=4 , B=2 , A/B=4/2=2/1 , so P/Q=2/1 , p+q=2+1=3
2 : A=6 , B=15 , A/B= 6/15=2/5 , so P/Q=2/5 , p+q=2+5=7

Input :
first line contains an integer T (number of test cases)
On next T lines there are two integers A and B.

output :
For each test case print the value of P+Q

constraints :
1<=T<=100000
1<=A,B<=10^18