题目描述

考虑一个具有 $\frac{N(N+1)}{2}$ 个顶点和 $\frac{3N(N-1)}{2}$ 条边的图，其中 $N$ 是一个大于等于 $2$ 的整数。

• 顶点集合为 $\{(i, j) \mid 1 \leq i \leq N, 1 \leq j \leq i\}$。
• 在 $(i, j)$ 与 $(i + 1, j)$ 之间存在一条权值为 $a_{i,j}$ 的边（对于 $1 \leq i \leq N - 1$ 且 $1 \leq j \leq i$）。
• 在 $(i, j)$ 与 $(i + 1, j + 1)$ 之间存在一条权值为 $b_{i,j}$ 的边（对于 $1 \leq i \leq N - 1$ 且 $1 \leq j \leq i$）。
• 在 $(i, j)$ 与 $(i, j + 1)$ 之间存在一条权值为 $c_{i,j}$ 的边（对于 $2 \leq i \leq N$ 且 $1 \leq j \leq i - 1$）。

对于该图中的一条简单路径，其路径的权值定义为该路径所经过的各条边的权值的乘积。

确定满足以下条件的无序顶点对 $\{s, t\}$（$s \neq t$）的数量：从 $s$ 到 $t$ 的任意简单路径的权值都是一个平方数。

输入格式

输入以如下格式给出：

$$\begin{aligned} &N \\ &a_{1,1} \\ &a_{2,1} \ a_{2,2} \\ &\vdots \\ &a_{N-1,1} \ \cdots \ a_{N-1,N-1} \\ &b_{1,1} \\ &b_{2,1} \ b_{2,2} \\ &\vdots \\ &b_{N-1,1} \ \cdots \ b_{N-1,N-1} \\ &c_{2,1} \\ &c_{3,1} \ c_{3,2} \\ &\vdots \\ &c_{N,1} \ \cdots \ c_{N,N-1} \end{aligned}$$

• $2 \leq N \leq 1,000$
• $1 \leq a_{i,j}, b_{i,j}, c_{i,j} \leq 10^6$
• 所有输入值均为整数。

输出格式

输出答案。

2
1
2
2

1

3
1
2 3
4
5 6
7
8 9

0

提示

翻译由 DeepSeek V3.2 完成