Шоколадные плитки
Наверное, всем известно, что шоколад полезен для мозга человека. Поэтому участники национальной олимпиады страны Олимпия принесли на тур много плиток шоколада, чтобы гениальные идеи приходили к них быстрее. Но принесённого шоколада оказалось слишком много, и после тура в кабинете осталось N прямоугольных плиток, которые состояли из долек размерами 1×1. Двое участников решили съесть часть шоколада, что остался, но, учитывая то, что на протяжении тура они съели достаточно много шоколада, было решено сделать это у достаточно необычный игровой способ, по следующим правилам.
Участники выполняют определённые операции с шоколадными плитками по очереди: сначала первый, потом второй, опять первый и т.д. При своём ходе участник выбирает плитку шоколада, с кооторой он будет выполнять одну из следующих операций:
Разломать плитку на две; линия разлома должна проходить параллельно сторонам плитки и между дольками.
Отломать и съесть произвольную "строку" или "столбик" плитки, который не является крайним.
Отломать и съесть все дольки плитки, находящиеся на краю, но чтобы после этого от плитки оставалась по меньшей мере одна долька (минимальный размер плитки, с кооторой может быть выполнена такая операция – 3×3).
Никакая из этих операций не может быть выполнена с плиткой 1×1, поэтому все такие плитки остаются до конца игры. Проигрывает тот участник, который при своём ходе не сможет сделать никакой из приведённых операций.
Напишите программу, которая по информации о плитках шоколада, оставшихся после тура, определяет количество вариантов первого хода первого участника, которые гарантируют ему выигрыш, при соблюдении выигрышной стратегии в дальнейшем.
Входные данные
В первой строке содержится целое число N (1 ≤ N ≤ 100) - количество шоколадных плиток. Во второй строке содержится N пар целых чисел, каждая i-тая из которых задаёт длину и ширину i-ой плитки. Длина и ширина не меньше 1 и не превышают 100.
Выходные данные
Вывести одно целое число - количество вариантов первого хода первого участника, которые гарантируют ему выиграш, при соблюдении им оптимальной стратегии в дальнейшем.