题目背景

赛时提醒：如果您始终是 30pts，且使用了题目给的快速读入，请重新拷贝修改后的快速读入。

赛时提醒：本题如果解法正确，快读可能无法起到优化作用。

这个恐怕是将存在乃至于记忆切割成三十二颗的争夺黑白棋。

双方剩下的棋子数字都很小——也就是重要性很高吧。

			......
        
——哥哥为什么会让自己落单呢？她原本对此感到疑惑。

不过，在得知答案之后，那可以说是理所当然的做法。

首先，第一个理由极为单纯。

故意将记忆托付给对方，暂时屈居败势的目的是——

「……那种事……白……做不到啊……」

想像了一下，白露出悲伤的笑容，做出这个结论。

哥哥做的这些事，如果由白执行……白不觉得自己的精神能够保持正常。

自己仅仅因为哥哥从身旁消失，就甚至一度怀疑哥哥的存在。

——被忘掉的话还好。

——忘掉哥哥的话——白确信自己的精神会无法保持正常。

			......
            
（……这里……哥哥在……这里……）

即使是空无一物的空间，但是白确信，她感觉得到哥哥的位置。

白顿时眼眶一热，不过她强行忍住，继续思考。

（……然后这就是……第二个……同时也是……最大的……理由。）

白将写着【参】的棋子白色面朝上，用手指夹住。

哥哥是『白色还是黑色』，这个问题也不需要犹豫。

因为既然他将最后的棋局托付给『白』——那他当然是持白棋。

这个现在看不见，甚至无法认知的棋局。

既没有开始的记忆，也不知道盘面的经过如何。

不过哥哥故意下输，并且为了让白能获胜所可能下的棋步……

而对方看到之后，完全中了哥哥的计谋，被诱导而下的棋步……

然后，为了逆转，哥哥可能选择的所有位置分布。

将这些全部推测分析——仅用三步棋反败为胜。

			......
        
然后——原先失去一天半的记忆——逆流了回来——

题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

1
3 2

2

1
100 5

84

提示

样例 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;
}