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
For each test case output the Kth smallest element of the Farey sequence FN in a single line.