题目描述

$t$次询问，每次给出$n,m,p$，求$f(n,m)\ mod\ p$.

$$f(n,m)=\sum^n_{i=1}\sum_{j=1}^{\lfloor \frac n i \rfloor }\sum_{k|i} {j^mk^m\mu(k)} $$

$t\le10^3.\ 1\le n\le10^{10^3},0\le m\le10^{10^3},1\le p\le10^{16}$.

输入格式

• 第一行，一个整数t表示t次询问.
• 第2到第t+1行，三个整数p,n,m.

输出格式

对于每一个询问，输出一行，一个整数表示答案

样例

2
114 5141919 810 
65535 998244353 1000000007

63
15233

###数据范围(最大值)

$id$	$t$	$n$	$m$	$p$
$1-2$	$100$	$1000$	$1000$	$1000$
$3-4$	$10^3$	$10^5$		$10^9$
$5-7$	1	$10^{10^3}$		$10^{16}$
$8-10$	$10^3$