Ключ разблокировки — это последовательность, состоящая из двух или более неповторяющихся точек. Отрезки между соседними точками в ключе разблокировки не могут проходить через другую точку. Таким образом, в ключах разблокировки не могут соседствовать следующие пары точек (в любом порядке): {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-й отрезок.

Выходные данные
Выведите искомое число ключей разблокировки.