题目描述

给出一个整数 $n$，求所有满足 $n\mid x$ 且 $\sigma_0(x)=n$ 的正整数 $x$ 的和，并对 $P$ 取模（$\sigma_0(x)$ 为 $x$ 的正因子个数）。

如果满足条件的数有无穷个则输出 $-1$（不对 $P$ 取模）。

多组询问。

输入格式

第一行一个正整数 $T$，描述数据组数。

接下来 $T$ 行，每行两个正整数 $n$ 和 $P$。

输出格式

一共 $T$ 行，每行一个数，表示答案。

Samples

3
2 10007
3 10007
6 10007

2
9
30