Description

话说考古学家ZL走进了一个山洞…………

ZL在山洞深处发现了一组密码锁，并断定这里藏着数不清的宝藏。经过一番寻找，ZL发现该密码锁上写着一串阿拉伯数字，看起来这些数字中有着一些微妙的联系。于是他动用了120分脑细胞，凭着藐视一切IMO选手的强大逻辑推理能力，找到了规律，并破解了几个密码锁。

可ZL毕竟是人，他也是会累的呀T_T

况且他的GPS显示前方还有成百上千个密码锁~！！！！

于是他把问题简化了一下，求助于身为OI神犇的你。

{============================================}

数列a[n]由如下关系式定义：

a[0]=0;

a[n]=f(a[n-1])

其中f(x)是一个正整数系数的m次多项式

对任意给定的x和y，求a[x]和a[y]的最大公约数d

令s为d模x的余数，t为d模y的余数

给定r和一个奇质数p，保证r不是p的整数倍

废话完毕，现在我们的问题是：

求方程 (rx2+sx+t) mod p = 0

有几个模p意义下的正整数解

对每个函数y=f(x)将进行T次询问

Format

Input

输入文件包括T+3行

第一行一个正整数m

第二行m+1个正整数cm，…，c0，其中ci(i=m，m-1，…，0)表示f(x)中xi的系数

第三行一个正整数T，表示询问次数

以下T行每行4个正整数，分别表示x，y，r，p

//保证输入文件合法

Output

输出文件包含T行，每行仅输出一个整数表示方程有多少组解（模p的意义下）

Samples

1
2 1
1
4 8 7 3

0

Limitation

对于100%的数据，T<=1000，m<=10，x<y，x<=10^5，y<=10^8，p<=10^8。