题目描述

给定一个素数 \(p\)，定义集合 \(A\) 为：

\[ A = \{1, 2, \dots, p-1\} \]

当 \(p\) 为素数时， \(A\) 在乘法意义下构成一个循环群。设 \(g\) 为模 \(p\) 的最小原根，则对任意 \(x\in A\) 都存在唯一整数 \({e(x)}\) 满足

\[ x\equiv g^{e(x)}(mod \, p), {0 \le e(x) \le p-2} \]

定义函数：

\[ {f(x) = gcd(e(x), p-1)} \]

对于给定整数 \(k\)，定义集合：

\[ {S_k = \{x\in A|f(x) = k\}} \]

对于每个测试用例请你输出：

1.集合 \(S_k\) 的元素个数。

2.集合 \(S_k\) 里所有元素乘积对 \(p\) 取模的结果。

注意：若 \(S_k\) 为空集合，其集合乘积视为 \(1\)。

原根定义：设 \(m\) 是正整数， \(a\) 是整数，若 \(a\) 模 \(m\) 的阶等于 \(\varphi(m)\)，则称 \(a\) 为模 \(m\) 的一个原根。

输入格式

第一行包含一个整数 \(T\) （ \(1 \le T \le 5 \times 10^3\)） 表示测试用例。

接下来 \(T\) 行,每行包含两个整数： \(p, k\)。

• p 为素数且 \(2 \le p \le 10^9\)
• \(1 \le k \le p-1\)

输出格式

每个测试用例输出一行两个整数，用空格分隔。

样例输入

3
3 2
5 2
5 3

样例输出

1 1
1 4
0 1