“Oh! You meant “Spectacularly ignorant” in a nice way.” -Sherlock

Problem 3

Given a list L, let us denote by \(F(M)\) the minimum index P (1-based indexing), such that \(LCM(L[1], L[2], ..., L[P]) \ge M\). You need to handle T queries. In each query, you'll be given 2 integers N and M. For each query, the list L will be replaced by all the divisors of N. Answer for this query will be \(F(M)\).

Input:

First line of input contains a single integer T, denoting the number of test cases. Each of the next T lines contains 2 integers N and M.

Output:

For each query, print an integer \(F(M)\) in a new line.

Constraints:

\(1 \le T \le 10^6\)

\(1 \le M \le N \le 10^6\)