C. Yum Yum Numbers
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After studying the "Matrix Bel Lotus", Muhannad (not you, Nahhal) invented a new concept in numbers, the lotusency. The lotusency of an integer $$$Y$$$ is the number of times it can be square-rooted while still remaining an integer. For example:

  • Lotusency of $$$9$$$ is $$$1$$$ because $$$9 \rightarrow 3$$$.
  • Lotusency of $$$16$$$ is $$$2$$$ because $$$16 \rightarrow 4 \rightarrow 2$$$.
  • Lotusency of $$$5$$$ is $$$0$$$ because its square-root is not an integer.

Muhannad has an integer $$$X$$$, and he wants to maximize its lotusency. He can do the following operation at most $$$K$$$ times:

  • Choose any prime number $$$p$$$ and set $$$X = X \cdot p$$$.

What is the maximum lotusency he can obtain?

Input

The first line contains a single integer $$$tc \: (1 \leq tc \leq 2 \cdot 10^5)$$$ — the number of testcases.

The first and only line of each testcase consists of two integers $$$X,K \: (2 \leq X \leq 2 \cdot 10^5) (0 \leq K \leq 10^{18})$$$.

Output

For each testcase, print a single integer, the maximum lotusency Muhannad can obtain.

Example
Input
3
5 1
8 5
200000 1000000000000000000
Output
1
3
58