406197: GYM102307 K Kernel Of Love

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:

1. $$$x$$$ and $$$y$$$ are Fibonacci numbers.
2. They are attractive to each other but not too much, this holds true when $$$gcd(x,y) = 1$$$
3. They are not too different or too similar, this is achieved when $$$(x + y) \mod{2} = 1$$$
4. 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 first line of the input represents the number of test cases. Each case consists of a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ per line.

For each case print the number of perfect couples.

6
1
4
8
17
20
25

0
3
5
11
13
17