#485 Palindrome Addition

Statement

Statement language

For an integer $M \ge 2$ , let $\mathbb{Z}/M\mathbb{Z}$ denote the residue classes modulo $M$ . In this problem, every residue is represented by one of $0,1,\cdots,M-1$ .

A nonzero polynomial of degree $d$ ,

P(x)=a_0+a_1x+\cdots+a_dx^d \qquad (a_d\ne0),

is called a palindromic polynomial if $a_i=a_{d-i}$ for every $0\le i\le d$ . The zero polynomial is not considered palindromic.

You are given a nonzero polynomial over $\mathbb{Z}/M\mathbb{Z}$ ,

F(x)=c_0+c_1x+\cdots+c_Nx^N.

Construct an integer $K$ with $1\le K\le3$ and palindromic polynomials $P_1,P_2,\cdots,P_K$ such that

F(x)=P_1(x)+P_2(x)+\cdots+P_K(x).

All coefficient additions are performed modulo $M$ .

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, first print the number $K$ of palindromic polynomials used.

Then print $K$ lines. For the $j$ -th palindromic polynomial

P_j(x)=a_{j,0}+a_{j,1}x+\cdots+a_{j,d_j}x^{d_j},

Constraints

$1\le T\le300\,000$ .
$2\le M\le1\,000\,000\,000$ .

Subtasks

#	Score	Constraints
1	20	$M\le3$ . $N\le5$ . Over all test cases, $\sum(N+1)\le100$ .

Samples

Input

1
9 5
2 5 4 2 4 2

Output

3
2 4 1 1 4 2
1 4 4 1
8 6 8

All three printed polynomials are palindromic. Adding their coefficients modulo $9$ gives $2,5,4,2,4,2$ , which is exactly the input polynomial.