Farey Sequence Again

Time Limit: 5000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

      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.

Input

      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.

Output

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

Sample Input

3 2 1 100 68 101 69

Sample Output

1/2 2/83 1/42

Hint

lcy

Source

2008 Asia Chengdu Regional Contest Online

提交代码