Mr. Potato Head works on Unified Non-linear Algorithms about Love (UNAL). These algorithms are connected to a traditional machine learning branch called Kernel methods. Mr. Potato Head has discovered a Kernel function which measures the similarity of two persons and hence can predict the likelihood of them being a good couple. He has taken his discoveries one step forward, after running a Kernel algorithm over a vast database of Facebook profiles, he made some interesting (albeit scary) discoveries: every single human can be mapped bijectively to a Fibonacci number, which allowed him to derive a formula that tells if a couple will be happy for ever and ever.

The Fibonacci numbers are the sequence of numbers $\{F_k\}_{k=1}^\infty$ defined by the linear recurrence equation $$F_{k+2} = F_{k+1} + F_{k}$$ with $F_1 = F_2 = 1$.

A perfect couple is represented by two numbers $x$ and $y$ such that:

$x$ and $y$ are Fibonacci numbers.

They are attractive to each other but not too much, this holds true when $gcd(x,y) = 1$

They are not too different or too similar, this is achieved when $(x + y) \mod{2} = 1$

Their eternal combination leads to another human being, this means, another Fibonacci number. This happens when $x + y = z$ where $z$ is a Fibonacci number.

Mr. Potato Head is astonished with his discovery, he now wants to understand how many truly happy couples are there in the world. For a given $n$ he wants to know how many couples exist on the first $n$ human beings (i.e. the first $n$ Fibonacci numbers) such that all conditions above hold true.

The city of Porto will host the ICPC World Finals in 2019. One of the secret touristic spots in the city is the so-called "lake of the thousand bridges". Mr. Manoel Pontes (Pontes stands for "bridges" in Portuguese; this is amazingly his real name$\ldots$) built this wonder in the lake with a lifetime of hard work. The lake has many small islands. Mr. Manoel built small wooden bridges connecting the islands. In some cases, there are multiple bridges connecting some pairs of islands. Visitors enjoy themselves while promenading through the bridges and small islands. Besides, by walking through the bridges the visitors can go from one island to any other island.

Mr. Manoel wants to enhance this touristic attraction to get even more visitors. One of this ideas is to organize visitors games. He plans to have the following challenge: is it possible to start to walk from outside the lake, pass through all the bridges without repetition, and go back to the starting point (that is, back out of the lake)?

Before creating the attraction, he himself tried it over and over but could not find out if this was possible. To make the challenge even more interesting, Mr. Manoel will allow adding some bridges between some islands. He wants to know if, by adding some of these bridges, the walk he wants the game to have becomes possible. Your task in this problem is to decide if it is possible to choose some (possibly none) of these bridges that, when added, allow people to walk as described.