当前没有测试数据。

题目描述

小X参加了今年的 NOI Online，看到了这道题：

Kri 喜欢玩数字游戏。

一天，他在草稿纸上写下了 $\red{t}$ 对正整数 $\red{(x, y)}$，并对于每一对正整数计算出了 $\red{z=x\times y\times\gcd(x,y)}$。

可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 $\red{y}$ 都擦除了，还可能改动了一些 $\red{z}$。

现在 Kri 想请你帮忙还原每一组的 $\red{y}$，具体地，对于每一组的 $\red{x}$ 和 $\red{z}$，你需要输出最小的正整数 $\red{y}$，使得 $\red{z=x× y\times\gcd(x,y)}$。如果这样的 $\red{y}$ 不存在，也就是 Zay 一定改动了 $\red{z}$，那么请输出 -1。

聪明的小X当然（不）能做出来了。不过现在小X想知道，对于所有 $\red{x \in [1,n], z \in [1,m]}$ 的正整数对 $\red{(x,z)}$，有多少对可以还原出至少一个 $\red{y}$，这些 $\red{y}$（每一组只算最小的 $\red{y}$）的总和是多少。这下小X不会了，于是他来寻求你的帮助。

由于第二问的答案可能很大，你只需要算出它对 $\red{p}$ 取模后的结果。

输入格式

本题采用多组数据。

第一行，一个整数 $\red{T}$，表示数据总数。

接下来 $\red{T}$ 行，每行三个整数 $\red{n, m, p}$。

输出格式

$\red{T}$ 行，每行两个整数，表示两个答案。

样例

3
2 4 7
5 5 1009
10 20 1009

5 4
9 19
46 283

说明与提示

样例说明

对于第一组数据，符合要求的有 $\red{(1,1),(1,2),(1,3),(1,4),(2,2)}$，对应的 $\red{y}$ 分别是 $\red{1,2,3,4,1}$。

对于第二组数据，符合要求的有 $\red{(1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(3,3),(4,4),(5,5)}$，对应的 $\red{y}$ 分别是 $\red{1,2,3,4,5,1,1,1,1}$。

数据范围

$\red{1 \le T \le 5, 1 ≤ n,m < 2^{32},2 < p < 10^9 + 10}$ 且 $\red{p}$ 是质数。