Farey Sequence Again

      The Farey sequence Fn for any positive integer n is the set of irreducible rational numbers a/b with 0<a<b<=n and (a, b) = 1 arranged in increasing order. Here (a, b) mean the greatest common divisor of a and b. For example:
            F2 = {1/2}
            F3 = {1/3, 1/2, 2/3}
      Given two positive integers N and K, with K less than N, you need to find out the K-th smallest element of the Farey sequence FN.

      The first line of input is the number of test case T, 1<=T<=1000. Then each test case contains two positive integers N and K. 1<=K<N<=10^9.

      For each test case output the Kth smallest element of the Farey sequence FN in a single line.

3
2 1
100 68
101 69

1/2
2/83
1/42

2008 Asia Chengdu Regional Contest Online