Description

数字之王大赛今天正式开始。

游戏规则是这样的：

• 一个好的数字 $x$ 要满足 $x\%\lfloor\sqrt[k] x\rfloor==0$
• 求 $1$ 到 $n$ 内有多少个好的数字，包含 $1$ 和 $n$

游戏规则非常简单，请你写个程序来解答吧

Input Format

有 $T(1\le T\le 100)$ 组样例

对于每组样例

输入两个整数 $n,k(1\le n,k\le 1E9)$

Output Format

对于每组样例在单独一行输出一个整数表示答案

2
7 2
7 3

5
7

Source

Online Judge http://127.0.0.1