P7893 『JROI-3』Reversi

**赛时提醒：如果您始终是 30pts，且使用了题目给的快速读入，请重新拷贝修改后的快速读入。** **赛时提醒：本题如果解法正确，快读可能无法起到优化作用。** 这个恐怕是将存在乃至于记忆切割成三十二颗的争夺黑白棋。 双方剩下的棋子数字都很小——也就是重要性很高吧。 ...... ——哥哥为什么会让自己落单呢？她原本对此感到疑惑。 不过，在得知答案之后，那可以说是理所当然的做法。 首先，第一个理由极为单纯。 故意将记忆托付给对方，暂时屈居败势的目的是—— 「……那种事……白……做不到啊……」 想像了一下，白露出悲伤的笑容，做出这个结论。 哥哥做的这些事，如果由白执行……白不觉得自己的精神能够保持正常。 自己仅仅因为哥哥从身旁消失，就甚至一度怀疑哥哥的存在。 ——被忘掉的话还好。 ——忘掉哥哥的话——白确信自己的精神会无法保持正常。 ...... （……这里……哥哥在……这里……） 即使是空无一物的空间，但是白确信，她感觉得到哥哥的位置。 白顿时眼眶一热，不过她强行忍住，继续思考。 （……然后这就是……第二个……同时也是……最大的……理由。） 白将写着【参】的棋子白色面朝上，用手指夹住。 哥哥是『白色还是黑色』，这个问题也不需要犹豫。 因为既然他将最后的棋局托付给『白』——那他当然是持白棋。 这个现在看不见，甚至无法认知的棋局。 既没有开始的记忆，也不知道盘面的经过如何。 不过哥哥故意下输，并且为了让白能获胜所可能下的棋步…… 而对方看到之后，完全中了哥哥的计谋，被诱导而下的棋步…… 然后，为了逆转，哥哥可能选择的所有位置分布。 将这些全部推测分析——仅用三步棋反败为胜。 ...... 然后——原先失去一天半的记忆——逆流了回来——

**白**在和森精种玩黑白棋，但黑白棋的规则有所改变。 有 $n$ 个黑白棋子，第 $i$ 个棋子编号为 $i$。棋子初始全为黑，游戏中，仅由**白**一人操作，**白**希望尽可能多的把棋子变成白色。 **白**要求第 $k$ 个棋子和第 $k \times p$ 个不能同时变成白色。 **白**共玩了 $T$ 次，每次**白**想知道最多能把多少棋子变成白色。**每次游戏独立。** 为避免混淆，加粗的**白**是人名。

第一行一个正整数 $T$，表示数据组数。 下面 $T$ 行每行两个整数 $n,p$，同题意。

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

#### 样例 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'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch