Напевно, всім відомо, що шоколад корисний для мозку людини. Тому учасники національної олімпіади країни Олімпія принесли на тур багато плиток шоколаду, щоб ґеніальні ідеї приходили до них швидше. Але принесеного шоколаду виявилося забагато, і після туру в кабінеті залишилося N прямокутних плиток, які складалися з часток розмірами 1×1. Двоє учасників вирішили з'їсти частину шоколаду, що залишився, але, враховуючи те що протягом туру вони скуштували досить багато шоколаду, було вирішено зробити це у досить незвичайний ігровий спосіб, за наступними правилами.

Учасники виконують певні операції з шоколадними плитками по черзі: спочатку перший, потім другий, знову перший і т.д. У свою чергу учасник обирає плитку шоколаду, з якою він буде виконувати одну з наступних операцій:

1. Розламати плитку на дві; лінія розлому повинна проходити паралельно сторонам плитки та між частками.
2. Відламати та з'їсти довільний «рядок» або «стовпчик» плитки, який не є крайнім.
3. Відламати та з'їсти всі частки плитки, що знаходяться з краю, але щоб після цього від плитки залишилася принаймні одна частка (мінімальний розмір плитки, з якою може бути виконана така операція – 3×3).

Жодна з цих операцій не може бути виконана з плиткою 1×1, тому всі такі плитки залишаються до кінця гри. Програє той учасник, який у свою чергу не зможе зробити жодної з наведених операцій.

Напишіть програму, яка за інформацією про плитки шоколаду, що залишилися після туру, визначає кількість варіантів першого ходу першого учасника, які ґарантують йому виграш, при дотриманні виграшної стратегії в подальшому.

Вхідні дані

У першому рядку міститься ціле число N (~1\leqslant N\leqslant 100~) – кількість шоколадних плиток. У другому рядку містяться N пар цілих чисел, кожна i-та з яких задає довжину та ширину i-ої плитки. Довжина та ширина не менші за 1 та не перевищують 100.

Результати

У єдиному рядку повинно міститися ціле число – кількість варіантів першого ходу першого учасника, які ґарантують йому виграш, при дотриманні оптимальної стратегії в подальшому.

Приклад

Вхід

1
3 3

Результат

3

Виграшні ходи першого учасника наступні:

• операція (3),
• операція (2) з другим рядком,
• операція (2) з другим стовпчиком.

(Це різні варіанти першого ходу, а не послідовність ходів.)