当前没有测试数据。

题目描述

有一个积性函数 $f$，$f(1)=1$，$f(p^k)=p^k\bmod (p+C)$，$C$ 是常数，给定 $n,C$，求 $\sum_{i=1}^nf(i)$。

输入格式

第一行输入一个正整数 $T$。

以下 $T$ 行，每行两个正整数 $n,C$。

输出格式

输出 $T$ 行，每行对应积性函数前缀和的值。

2
100 114514
12 1

5050
52

样例解释

对于第二组测试数据，$f(1)=1$，$f(2)=2$，$f(3)=3$，$f(4)=1$，$f(5)=5$，$f(6)=6$，$f(7)=7$，$f(8)=2$，$f(9)=1$，$f(10)=10$，$f(11)=11$，$f(12)=3$。

数据范围

对于 $10\%$ 的测试数据，$1\le n\le 10^7$。

对于另外 $10\%$ 的测试数据，$C=2^{31}-1$。

对于 $100\%$ 的测试数据，$1\le T\le 5$，$1\le n,C\le 2^{31}-1$。