Chocolate bars#677
Probably everyone knows that chocolate is good for the human brain. Therefore, participants of the national Olympiad brought many chocolate bars to the contest so that great ideas would come to them faster. However, too much chocolate was brought, and after the contest, rectangular chocolate bars remained in the office, each consisting of 1 \times 1 pieces. Two participants decided to eat some of the remaining chocolate, but since they had eaten enough chocolate during the contest, they decided to do so in a rather unusual game, according to the following rules.
Participants take turns making moves: first the first participant, then the second, then the first again, and so on. On their turn, a participant chooses a chocolate bar and performs one of the following operations:
Break the bar into two pieces; the break line must be parallel to the sides of the bar and go between the pieces.
Break off and eat any "row" or "column" of the bar that is not at the edge.
Break off and eat all the pieces of the bar that are on the edge, but after this, at least one piece must remain (the minimum size of a bar for this operation is 3 \times 3).
None of these operations can be performed on a 1 \times 1 bar, so all such bars remain until the end of the game. A participant who cannot make any operation on their turn loses.
Write a program that, given the information about the chocolate bars remaining after the contest, determines the number of options for the first move of the first participant that guarantee a win for them, assuming an optimal strategy is followed in the future.
The first line contains an integer (1 \leq N \leq 100) — the number of chocolate bars. The second line contains pairs of integers, each pair giving the length and width of the corresponding bar. Length and width are at least and at most .
Output a single integer — the number of possible first moves for the first participant that guarantee a win for them, assuming an optimal strategy in the future.
Example 1