행렬 악몽

오비완이라면 이렇게 말했을 것이다: "이것은 네가 찾는 문제 설명이 아니다. 그냥 지나가라."

이중 팩토리얼 수는 다음 점화식으로 정의되는 수 $d_i$이다: $d_0 = 1$, 그리고 모든 $i > 0$에 대해 $d_i = d_{i-1} \cdot i!$. 예를 들어 $d_3 = 1! \cdot 2! \cdot 3! = 12$이다.

모든 원소가 집합 $\{0, \dots ,n-1\}$에 속하는 길이 $n$의 수열을 차수 $n$의 제한 수열이라고 한다. 예를 들어 $(0, 2, 0, 1)$은 차수 $4$의 제한 수열이다. 차수 $n$의 모든 제한 수열의 집합을 $S_n$으로 적는다.

수열 $A = (a_0, \dots , a_{n-1})$의 확산 인자는 $\sigma(A) = \prod_{i=0}^{n-1}\prod_{j=i+1}^{n-1}(a_i - a_j)$이다.

수열 쌍과 쌍의 수열 사이에는 직접적인 동형 대응이 있다. $A, B \in S_n$이고 $A = (a_0, \dots , a_{n-1})$, $B = (b_0, \dots , b_{n-1})$이라 하자. 대응하는 쌍의 수열 $((a_0, b_0), \dots ,(a_{n-1}, b_{n-1}))$을 $P_{A,B}$로 적는다.

정수 쌍은 사전식으로 비교한다. $(a, b) \le (c, d)$는 $a < c$이거나 ($a = c \land b \le d$)인 경우를 뜻한다. 정수 쌍의 수열 $P = (p_0, \dots , p_{n-1})$이 모든 $i$에 대해 $p_i \le p_{i+1}$을 만족하면 $P$는 사전식으로 정렬되어 있다고 한다. $\rho(P) =$ [$P$가 사전식으로 정렬되어 있으면 $1$, 아니면 $0$]으로 정의한다.

행과 열을 $0$부터 $n - 1$까지 번호 매긴 $n \times n$ 행렬 $M$을 생각하자. 원소는 $m_{r,c}$로 적는다. 각 원소가 정수이거나 변수인 행렬을 $\mathbb{Z}$-var 행렬이라고 한다. $M$의 $n$단계 순회 가중치는 다음과 같다.

$\varphi(M) = \frac{1}{d_{n-1}^2} \cdot \sum_{A=(a_0,\dots ,a_{n-1}), A \in S_n} \sum_{B=(b_0,\dots ,b_{n-1}), B \in S_n} \left( \rho(P_{A,B}) \cdot |\rho(A)| \cdot \rho(B) \cdot \prod_{i=0}^{n-1} m_{a_i,b_i} \right)$

정수 계수의 다변수 다항식 $p$가 주어진다. $\varphi(M) = p$가 되는, 충분히 작은 $\mathbb{Z}$-var 행렬 $M$을 하나 구하라.

첫 줄에는 테스트 케이스의 개수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.

각 테스트 케이스는 다항식을 설명하는 한 줄로 이루어진다. 변수는 a부터 z까지의 알파벳 문자이며, 문법은 입력 파일에서 명확하게 드러난다. 각 다항식의 연산(덧셈, 뺄셈, 곱셈)은 50개 미만이다.

각 테스트 케이스마다 행렬 하나를 다음 형식으로 출력한다. 먼저 크기 $n$을 쓰고, 이어서 모든 원소를 행 우선 순서로 쓴다. 원소 사이에는 양의 길이를 가진 공백이 몇 개든 들어갈 수 있다. 행렬의 크기는 $70$을 넘을 수 없다. 모든 정수는 $-10^9$ 이상 $10^9$ 이하여야 한다.

주어진 다항식에 대해 그런 행렬이 존재하지 않으면 대신 $0$ 하나만 출력한다.