题目描述

小利准备将 n块拼图从左到右进行拼接，每块拼图原本为大小一致的正方形卡片，每条边都做了改变，共有8种不同的边，使用编号1~8表示。每块拼图使用其上、右、下、左四条边的编号来表示。

例如，下面两块拼图共有8种不同的边，左边的拼图用编号1234 表示，右边的拼图用5678 表示:

拼图规则： 1）在拼图中，1号边只能与8号边拼接，2号边只能与7号边拼接，3号边只能与6号边拼接，4 号边只能与5号边拼接，如下图所示：

2）你可以将每块拼图顺时针旋转0度、90度、180度、270 度来进行拼图(不能翻转到另一面进行拼图)；

例如，下图是同一块拼图旋转不同度数时的效果:

3）除第一块拼图外，下一块拼图只能拼在已拼接拼图的最右边。

给定一个整数 n，表示拼图的块数，以及n个长度为 4，仅包含数字 1~8 的字符串，分别表示每块拼图上、右、下、左 4 条边的编号。请计算小利要将n块拼图从左至右拼完，一共有多少种不同的拼法。

注：在各种拼法中，只要有任意一个相同位置上的拼图不一致或拼图相同但旋转的方向不一致，都算不同的拼法。

本题中，n块拼图是不同的，不存在以下两种情况：

1)同一块拼图，旋转90 度、180 度、270 度后，不会出现与0 度相同的情况；

2)任意两块拼图，不会出现其中一块拼图旋转后与另一块相同。

例如：n=3；3块拼图分别是 4524、6134、3872，如下图所示：

一共有 4 种不同的拼法，如下图所示：

输入描述

第一行输入一个整数 n（2 ≤ n ≤ 8），表示拼图的块数；

第二行输入 n 个长度为 4 的字符串，字符串仅包含数字 1 - 8，字符串之间以一个空格隔开，每个字符串从左至右的 4 个数字依次表示该块拼图 上、右、下、左 四条边的编号。

输出描述

输出一个整数，表示多少种不同的拼法。

样例

3
4524 6134 3872

4

提示

本题10 组测试用例，每通过一题得 8 分。