丢丢陈有一个长度为n的数列 a1,…,ana_1,\ldots ,a_na1,…,an ,和两个数字 P,QP,QP,Q。由于丢丢陈很无聊他先对每个数字进行了如下操作
丢丢陈很想了解这个数列，他想知道数列的和对 QQQ 取余数的结果，即 (a1+a2+…+an) mod Q(a_1+a_2+\ldots +a_n)\ mod\ Q(a1+a2+…+an) mod Q。
其中，modmodmod 为取余运算符，a mod ba\ mod\ ba mod b 的结果为 aaa 除 bbb 后的余数，例如 10 mod 3=110\ mod\ 3 = 110 mod 3=1。
第一行仅有一个数字 T(1≤T≤3)T(1\le T\le 3)T(1≤T≤3) 代表数据组数。下面依次是每一组数据
每组数据第一行三个数字 n,P,Q(2≤n≤105,1≤P≤1018,1≤Q≤109)n,P,Q(2\le n \le 10^5,1\le P \le 10^{18},1\le Q \le 10^9)n,P,Q(2≤n≤105,1≤P≤1018,1≤Q≤109)。
第二行 nnn 个数字 ai(0≤ai≤1018)a_i(0\le a_i \le 10^{18})ai(0≤ai≤1018)。
每组数据仅一行，代表变换后数列的和对 QQQ 取余数的结果。
1 5 101 17 1 1 2 1 3
11
