GuGu Convolution

As a newbie, XianYu is now learning generating function!
Given a series $\{a\}=(a_0,a_1,a_2,\cdots)$, we can easily define its exponential generating function as $g_{\{a\}}(x) = \sum\limits_{i=0}^{\infty}\dfrac{a_i}{i!}x^i$.
Now we define a series $\{u_c\}=(c^0,c^1,c^2,\cdots)$ and let $e_c$ represents the ${u_c}$ with $0$ filled in all its even items. Formally, ${\{e_c\}}=(0,c^1,0,c^3,0,c^5,\cdots)$.

'Do you know convolution?'
'GU GU.' GuGu utters.
'Well, let me show you.
Given two generating function $g_{\{a\}}$ and $g_{\{b\}}$, the convolution can be represented as $G(x)=(g_{\{a\}}*g_{\{b\}})(x)=\sum\limits_{n=0}^{\infty}(\sum\limits_{i+j=n}a_ib_j)x^n$.
It is quite easy, right?'
'GU GU.' GuGu utters.
'Ok. Now you have to find the coefficient of $x^n$ of the convolution $G(x)=(g_{\{u_A\}}*g_{\{e_\sqrt{B}\}})$, given $n$, $A$ and $B$.
Let $G_n$ representes that coefficient, you should tell me $n!G_n$.
You may know the severity of unsolving this problem.'

As GuGu is not that kind of good for it, it turns to you for help.
'GU GU!' GuGu thanks.

There is an integer $T$ in the first line, representing the number of cases.
Then followed $T$ lines, and each line contains four integers $A,B,n,p$. The meaning of $A,B,n$ is described above, and that of $p$ will be described in Output session.
$1\leq T \leq 10^5$
$1\leq A,B \leq 10^6$
$1\leq n \leq 10^{18}$
$1\leq p \leq 10^{9}$

Let $\sum\limits_{i=1}^{q} a_i\sqrt{b_i}$ represents the answer, with $b_i \neq b_j, \gcd(b_i,b_j)=1, 1\leq i< j\leq q$, and none of $b_i$'s factors is square number.
Print $T$ lines only. Each line comes with a number $q$ and followed $q$ pairs of integers $a_i$ $b_i$, with $b_i$ in increasing order. Since $a_i$ may be large, please print $a_i\%p$ instead. All integers in the same line should be seperated by exactly one space.
You may find that each answer is unique.

3
1 1 1 7
523 12 2 2100
1 1 1000000000000000000 998244353

1 1 1
1 2092 3
1 121099884 1

2018中国大学生程序设计竞赛 - 网络选拔赛