Problem Description

Xiao Y has a combination lock with five dials. As shown in the figure, each dial contains digits from $0$ to $9$. Each dial is cyclic from $0$ to $9$, meaning that after turning $9$ by one position it can become $0$ or $8$.

Because the campus is relatively safe, Xiao Y locks his bike in the following way: starting from the correct password, he randomly turns the lock exactly once. Each time, he turns either one dial by some amount, or two adjacent dials at the same time by the same amount.

When Xiao Y chooses to turn two adjacent dials at the same time, the two dials are turned by the same amount. For example, he can change the lock from $\tt{0\;0\;1\;1\;5}$ to $\tt{1\;1\;1\;1\;5}$, but not to $\tt{1\;2\;1\;1\;5}$.

Over time, Xiao Y also worries about the security of locking the bike this way, so he wrote down $n$ states of the lock after locking. Note that none of these $n$ states is the correct password.

To test how secure this locking method is, how many possible correct passwords are there, such that each correct password can generate all of the given $n$ lock states after locking, following Xiao Y’s locking method.

Input Format

The first line contains a positive integer $n$, indicating the number of lock states after locking.

The next $n$ lines each contain five integers, describing one state of the combination lock.

Output Format

Output one line containing one integer, indicating how many possible correct passwords can correspond to these $n$ states under the given locking method.

1
0 0 1 1 5

81

Hint

[Sample 1 Explanation].

There are $81$ possible solutions in total.

Among them, there are $45$ solutions that turn only one dial, and $36$ solutions that turn two dials.

[Sample 2].

See lock/lock2.in and lock/lock2.ans in the contestant directory.

[Constraints].

For all testdata: $1 \leq n \leq 8$.

Special Property A: It is guaranteed that all correct passwords can obtain the given $n$ states by turning only one dial.

Translated by ChatGPT 5