Экран блокировки телефона состоит из 9 пронумерованных точек, расположенных в три ряда по три штуки в каждом.
Ключ разблокировки — это последовательность, состоящая из двух или более неповторяющихся точек. Отрезки между соседними точками в ключе разблокировки не могут проходить через другую точку. Таким образом, в ключах разблокировки не могут соседствовать следующие пары точек (в любом порядке): {1, 3}, {4, 6}, {7, 9}, {1, 7}, {2, 8}, {3, 9}, {1, 9}, {3, 7}. На экране телефона между некоторыми парами точек видны отрезки со следами от пальца, — значит, такая пара точек должна присутствовать в ключе разблокировки, причём на соседних позициях (в любом порядке).
Посчитайте, сколько существует ключей разблокировки, удовлетворяющих условию задачи. Гарантируется, что ответ не будет равен нулю.
В первой строке задано число отрезков со следами от пальца N (0 ≤ N ≤ 8).
В следующих N строках заданы отрезки в виде пар чисел Ai, Bi (1 ≤ Ai, Bi ≤ 9) — точек, между которыми проходит i-й отрезок.
Выведите искомое число ключей разблокировки.
6
1 8
8 7
7 5
4 5
2 4
2 6
6
4
3 5
5 2
2 6
6 1
110
На рисунке изображено расположение отрезков в первом примере. Подходящие ключи: 1875426, 18754263, 18754269, 36245781, 6245781, 96245781.
