Meteor

Though time passes, there is always someone we will never forget.
"The probability of being hit by a meteor is one in a billion, but it is much more miraculous, to meet you in my life." said Tom to Jerry with affection.
"One in a billion? I may not agree with you." answered Jerry proudly, "Let's do the math."
...
Thinking of the days they have happily spent together, Tom can't help bursting into tears. Though Jerry has been gone for a long time, Tom still misses him every day. He remembers it was a sunny afternoon when Jerry and him were lying in the yard, working on the probability of a man being hit by a meteor.
Unlike Jerry, he was always slow. Jerry got the answer soon, but Tom was stuck as usual. In the end, Tom lost patience and asked Jerry to tell him the answer.
"I can't be so straightforward," snickered Jerry, "the only thing I will tell you is that the answer is $\frac pq$, where $p,q\le n,\gcd(p,q)=1$."
"Is it $\frac {1}{n}$?"
"Is it $\frac {1}{n-1}$?"
...
If answered "No" , he would try the minimum larger number that satisfies the requirement.
Tom only remembered $n$ given by Jerry, and $k$, the times that he tried, but forgot what matters the most: Jerry's answer. Now, he wants you to help him find it.

The first line contains an integer $T(T\le 10^2)$, the number of test cases.
The next $T$ lines, each line contains two numbers, $n,k(2\le n\le 10^6)$, indicating a query.
The answer is guaranteed to be in $(0,1]$.

$T$ lines, each line contains a fraction in term of p/q ,where $\gcd(p,q)=1$.

5
4 6
5 1
9 9
3 4
7 11

1/1
1/5
1/3
1/1
3/5

g++ compiler on HDOJ supports __int128.

2019 Multi-University Training Contest 1