As Obi-Wan would put it: “This isn’t the problem statement you are looking for. Move along.”

The double factorial numbers are the numbers d_{i} deﬁned by the following recursive formula: d_{0} = 1, and
∀i > 0 : d_{i} = d_{i−1} ⋅ i!. For example, d_{3} = 1! ⋅ 2! ⋅ 3! = 12.

Sequences of length n with all elements belonging into the set {0,….n − 1} are called limited sequences of
order n. For example, (0,2,0,1) is a limited sequence of order 4. The set of all limited sequences of order n will
be denoted 𝒮_{n}.

The spread factor of a sequence A = (a_{
0},…,a_{n−1}) is the value σ(A) = ∏
_{i=0}^{n−1} ∏
_{j=i+1}^{n−1}(a_{i} − a_{j}).

There is a direct isomorphism between pairs of sequences and sequences of pairs. Formally: Let A,B ∈𝒮_{n}.
We can denote their elements as follows: A = (a_{0},…,a_{n−1}), B = (b_{0},…,b_{n−1}). The corresponding sequence of
pairs (a_{0},b_{0}),…,(a_{n−1},b_{n−1}) will be denoted P_{A,B}.

Pairs of integers can be ordered lexicographically in the usual fashion: (a,b) ≤ (c,d) if either a < c, or
(a = c∧b ≤ d). A sequence P = (p_{0},…,p_{n−1}) of pairs of integers is ordered lexicographically if for all i, p_{i} ≤ p_{i+1}.
Let ρ(P) = [if P is ordered lexicographically then 1 else 0].

Let M be a n × n matrix, with rows and columns indexed from 0 to n − 1. Elements of M will be denoted
m_{r,c}. A matrix is called a ℤ-var matrix if each element in the matrix is either an integer or a variable. The
n-step traversal weight of M is the following value:

Problem speciﬁcation

Given is a multivariate polynomial p with integer coeﬃcients. Produce any reasonably small ℤ-var matrix M such that φ(M) = p.

Input speciﬁcation

The ﬁrst line of the input ﬁle contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line describing the polynomial. The variables are the letters a through z, the syntax will be clear from the input ﬁle. Each polynomial in the input ﬁle contains less than 50 operations (i.e., additions, subtractions and multiplications).

Output speciﬁcation

For each test case output one matrix in the following format: First its size n, then all its elements in row
major order. The elements may be separated by any positive amounts of whitespace. The size of the matrix must
not exceed 70. All integers must be between −10^{9} and 10^{9}, inclusive.

If for a given polynomial no such matrix exists, output a single zero instead.

Example

input

1

xy

xy

output

2

1 y

x 0

1 y

x 0