“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$