Полимино — это связная фигура из n равных квадратов, соединённых сторонами. Неформально, это связное множество клеток, которое можно вырезать из бесконечного листа клетчатой бумаги. Два полимино считаются совпадающими, если одно из них можно перевести в другое с помощью параллельных переносов, поворотов или отражений относительно прямой, параллельной одной из осей координат (которым параллельны все стороны всех квадратиков). Набор n-полимино считается полным, если никакие два полимино в наборе не являются совпадающими и любое добавленное в набор n-полимино будет совпадать с каким-нибудь из имеющихся.
Например, полный набор 3-полимино состоит из двух фигур,
а полный набор 4-полимино состоит из пяти фигур.
У Алёны есть полный набор n-полимино. Она считает некрасивыми все полимино, содержащие квадрат 2 × 2. По заданному n определите количество некрасивых полимино.
Первая строка входа содержит одно целое число n — параметр набора полимино (3 ≤ n ≤ 7).
Выведите одно целое число — количество некрасивых n-полимино.
3
0
4
1
Так как в квадрате 2 × 2 4 клетки, а в 3-полимино 3 клетки, то ни одно 3-полимино не содержит квадрата 2 × 2.
Единственным 4-полимино, содержащим квадрат 2 × 2, является сам квадрат 2 × 2.
