给定一个整数 $n \ge 2$。在二维平面上构建点集 $(i, j)$，满足 $1 \le i \le n$ 且 $1 \le j \le i$。考虑一个以这些点为顶点、包含以下边构建的无向带权图：

• 在 $(i, j)$ 和 $(i + 1, j)$ 之间有一条权值为 $a_{i,j}$ 的边（其中 $1 \le i \le n - 1$ 且 $1 \le j \le i$）。
• 在 $(i, j)$ 和 $(i + 1, j + 1)$ 之间有一条权值为 $b_{i,j}$ 的边（其中 $1 \le i \le n - 1$ 且 $1 \le j \le i$）。
• 在 $(i, j)$ 和 $(i, j + 1)$ 之间有一条权值为 $c_{i,j}$ 的边（其中 $1 \le i \le n$ 且 $1 \le j \le i - 1$）。

作为参考，该图有 $n(n + 1)/2$ 个顶点和 $3n(n - 1)/2$ 条边。

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

求无序顶点对 $\{s, t\}$（$s \neq t$）的数量，使得 $s$ 和 $t$ 之间的每条简单路径的权值都是完全平方数。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 1000$）。

接下来 $n - 1$ 行。其中的第 $i$ 行包含 $i$ 个整数，表示 $a_{i,j}$（$1 \le j \le i$），满足 $1 \le a_{i,j} \le 10^6$。

接下来又是 $n - 1$ 行。其中的第 $i$ 行包含 $i$ 个整数，表示 $b_{i,j}$（$1 \le j \le i$），满足 $1 \le b_{i,j} \le 10^6$。

接下来又是 $n - 1$ 行。其中的第 $i$ 行包含 $i$ 个整数，表示 $c_{i+1,j}$（$1 \le j \le i$），满足 $1 \le c_{i+1,j} \le 10^6$。

输出格式

输出一个整数，表示该问题的答案。

样例

输入样例 1

2
1
2
2

输出样例 1

1

输入样例 2

3
1
2 3
4
5 6
7
8 9

输出样例 2

0