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

Figure 1: Combination lock

Because the campus is relatively safe, Little Y's method for locking the bike is as follows: starting from the correct password, rotate the lock randomly exactly once; each time, rotate only one dial by a certain amount, or rotate two adjacent dials by the same amount.

When Little Y chooses to rotate two adjacent dials simultaneously, both dials are rotated by the same amount. That is, Little Y can change the combination from 0 0 1 1 5 to 1 1 1 1 5, but not to 1 2 1 1 5.

After a long time, Little Y became worried about the security of this locking method, so he recorded $n$ states of the lock after he locked it. Note that none of these $n$ states is the correct password.

To test the security of this locking method, how many possible correct passwords are there such that each correct password could produce all $n$ recorded states of the lock according to his locking method?

Input

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

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

Output

Output a single integer representing how many correct passwords can correspond to these $n$ states according to the given locking method.

Examples

Input 1

1
0 0 1 1 5

Output 1

81

Note 1

There are 81 possible combinations in total. Among them, there are 45 ways by rotating one dial, and 36 ways by rotating two adjacent dials.

Input 2

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

Constraints

For all test data, $1 \le n \le 8$.

Special Property A: It is guaranteed that all correct passwords can be obtained by rotating only one dial to reach the $n$ states provided in the test data.