GRUPVIVA  Group Viva
Today is external viva of computer science subject and Bosky is not at all prepared for it. Adding to his problems, he hasn't reached college yet. Luckily the external examiner was late too. Bosky somehow managed to reach the college before the external examiner arrived but he was still worried because he didn't want to get insulted by external examiner.
The procedure for the conducting of viva is that each student has to sign the attendance register regardless of their given roll number before entering the viva room. Then they will be called individually or in groups of equal students exactly in the same order as they signed in the attendance register. It should be ensured by the internal invigilator that signing in the attendance register by the students has to be done before the external examiner arrives. The viva exam will start immediately only after the arrival of the external examiner. Students were informed that external examiner will arrive exactly after 30 mins. Bosky got some extra time to think how he can save himself from being insulted in front of the external examiner. He looked around and found that there were few students who were in worse condition than he himself was. With his past experience he concluded that on being called in groups the external picks up the most vulnerable student among the group and keeps on insulting and cursing the same student, ignoring the rest. Bosky knew that if he could manage to be in group with a student who is more vulnerable than him then he might get ignored by the external.
When everybody started signing the attendance register, Bosky quickly looked around and spotted such a student and signed after him in the attendance register. He is quite certain now that if he has to give viva in a group in which both of them are present he might save himself from being insulted.
There are "N" students in his class and Bosky knows that external examiner will call everyone in group of "X" students at once,where X can be any number between [1,N] (both ends inclusive). Now he wonders what is the probability that he and his "prey" would be in the same group.
Given total number of students and Bosky's position in the attendance register, your task is to tell what is the probability that Bosky's plan will succeed i.e. he and his [so called] "prey" will be in same group.
More formally you are given two integers N and R ,where 2<=N<=10^9 and 2<=R<=N . You have to find the probability that R and (R1) will be in the same group if the sequence [1,2,3...N] is divided into group of "X" numbers sequentially i.e [1...N] is divided into groups [1...X],[(X+1)...2*X], [(2*X+1)...3*X] ... [ (X*floor((N1)/X)+1)...N] , where 1<=X<=N and last group can have less than X numbers.
Input:
Input will contain a number T denoting the number of test cases.
Then T test cases follow, each one consisting 2 integers N and R where N is the total strength of the class and R is Bosky's position in the attendance register.
Output
For each test case, output the probability as rational number of form p/q.The greatest common divisor of p and q should be 1.
Constrains
1<= T <=500
1< N <=10^9
1< R <=N
Sample Input
2
5 5
6 5
Sample Output
2/5
1/2
Explanation:
Case 1: N=5 and R=5
i.e. Total Students=5 and Bosky's has signed at 5th position
his pray signed before him hence he signed at 4th position
Suppose students are called in group of "X",where 1<=X<=N
For different values of "X" groups formed are as follow
For, X=1
[ {1},{2},{3},{4},{5} ]
X=2
[ {1,2} , {3,4} , {5} ]
X=3
[ {1,2,3} , {4,5} ]
X=4
[ {1,2,3,4} , {5} ]
X=5
[ {1,2,3,4,5} ]
We can clearly see that for X=3 and X=5 Bosky's plan will succeed i.e. he and his pray will be in same group. Hence the output is "2/5"
Case 2: Similar to Case 1 where N=6 and R=5
For, X=1
[ {1},{2},{3},{4},{5},{6} ]
X=2
[ {1,2} , {3,4} , {5,6} ]
X=3
[ {1,2,3} , {4,5,6} ]
X=4
[ {1,2,3,4} , {5,6} ]
X=5
[ {1,2,3,4,5}, {6} ]
X=6
[ {1,2,3,4,5,6} ]
Here Bosky's plan succeeds for X=3,X=5 and X=6.
Hence the output is "3/6" ==> "1/2" [Note: Output must be irreducible rational number]
hide comments
Anubhav Balodhi :
20140707 21:15:44
got tle with nÃ¤ive algo... still getting WA with an apt algo..


P_Quantum:
20140703 19:41:36
nice prblm 

J_P:
20140703 09:58:03
nice one.. :) 

Bhavik:
20140531 11:43:24
@ankush: int has got nothing to do with algo..it was only for speed comparison!


Ankush Sharma:
20140531 10:30:46
@Bhavik , tried int but no help.Which algo you have used ? 

Bhavik:
20140529 17:14:24
'int' is sufficient!


Ankush Sharma:
20140529 06:13:05
Getting TLE,need help !! 

raunakrocks:
20140528 21:33:16
Learnt about the logic ..nyce problem 

Ahmedali Durga:
20140523 07:52:40
I am getting TLE but i've tried the best optimization possible.. 

Manish Singh Bisht:
20140512 17:45:10
@Flago: I am glad :) 
Added by:  Manish Singh Bisht 
Date:  20140401 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 