Description

白在和森精种玩黑白棋，但黑白棋的规则有所改变。

有 $n$ 个黑白棋子，第 $i$ 个棋子编号为 $i$。棋子初始全为黑，游戏中，仅由白一人操作，白希望尽可能多的把棋子变成白色。

白要求第 $k$ 个棋子和第 $k \times p$ 个不能同时变成白色。

白共玩了 $T$ 次，每次白想知道最多能把多少棋子变成白色。每次游戏独立。

为避免混淆，加粗的白是人名。

Input Format

第一行一个正整数 $T$，表示数据组数。

下面 $T$ 行每行两个整数 $n,p$，同题意。

Output Format

共 $T$ 行，每行一个正整数，表示白最多能把多少枚棋子变为白色。

1
3 2

2

1
100 5

84

Hint

样例 1 解释

可以选择第 $2,3$ 个棋子变色。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$T \le 5$，$n \le 2$；
• Subtask 2（5 pts）：$T \le 5$，$n \le 10$；
• Subtask 3（20 pts）：$T \le 5$，$n \le 10^6$；
• Subtask 4（70 pts）：无特殊限制。

对于 $100\%$ 的数据满足，$1 \le T \le 10^6$，$0 \le n \le 10^{18}$，$1 \le p \le 10^{9}$。

//快读模板
//赛时提醒：快读没有太大必要使用
inline long long read(){
   long long s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}