Problem Description

Now it's time after math class!

The teacher taught Baby Volcano what can do with polynomials and how to use polynomials.The teacher said that a polynomial of degree $n$ can be written as $f(x)=\sum \limits_{i=0}^{n} a_i x^i$. Also,you can regard it as a function,and replace $x$ with some number $a$ in order to get a special value called $f(a)$

Today's math homework is to calculate $f(a)$ of a polynomial of degree $n$,$f(x)$.Because the answer is extremely large,Baby Volcano is only asked to write $f(x) \bmod p$ on the paper,where $p$ is a prime number.

Baby Volcano writes number $f(0) \bmod p,f(1) \bmod p,\cdots,f(n) \bmod p$ on a textbook quickly. After a while,however,he lost $f(x)$ and can't continue with his homework.

Baby Volcano want to find $f(x)$,But he is too small to solve it.Baby Volcano needs your help!

Input

The first line contains one integer $T(1 \le T \le 50)$ stand for the test cases you should solve.

For each test cases,the first line contains two integer $n,p(1 \leq n < p-1,3 \leq p \leq 5 \times 10^5)$.

The next line contains $n+1$ integer,the $i$-th stand for $f(i-1)$.

The input garantees that $\sum p \leq 10^6,p$ is prime,$0 \leq f(i) < p$.

Output

For each test case, you should firstly output "Case #t: "(without quotes), where $t$ is the index of this test case.

In the next line,you should output a single line contains $n+1$ integer.The $i$-th stands for $a_{i-1} \bmod p$.

It can be proved that there is only one solution if you modulo the coefficient by $p$,so there is and only one acceptable output.

3
2 10007
1 4 9
3 10007
1 8 27 64
12 10007
1 1 4 5 1 4 1 9 1 9 8 1 0

Case #1:
1 2 1
Case #2:
1 3 3 1
Case #3:
1 8594 9725 4829 7653 7268 9644 5003 6141 3793 9624 5125 2657