问题 S: Kernel Of Love
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:287
解决:139
题目描述
土豆头先生致力于研究关于爱的统一非线性算法(UNAL)。这些算法与传统的机器学习分支 "内核方法 "有关。土豆头先生发现了一个核函数,它可以衡量两个人的相似性,从而可以预测他们成为好夫妻的可能性。他将自己的发现向前推进了一步,在对庞大的Facebook个人资料数据库运行内核算法后,他有了一些有趣(尽管很可怕)的发现:每一个人都可以映射到一个斐波那契数,这使他能够得出一个公式,告诉人们一对夫妇是否会永远幸福下去。
斐波那契数是由线性递归方程定义的数字序列 ${F_n} $(n=1,2,3...)
有 $F_{k+2}=F_{k+1}+F_k$ $with$ $F_1=F_2=1$
一对完美的夫妇是由两个数字x和y表示的。
(1)$x$和$y$是斐波那契数。
(2)它们相互吸引,但不是太多,当 $gcd(x,y)=1$ 时,这一点成立。
(3)它们没有太大差别或太过相似,当 $(x+y)$ $mod$ $2=1$ 时,这一点就成立了
(4)他们的永恒组合导致了另一个人,这意味着,另一个斐波那契数。这发生在 $x+y=z$ 的时候,其中$z$是斐波那契数。
土豆头先生对他的发现感到惊讶,他现在想了解世界上有多少对真正幸福的夫妇。 对于给定的$n$,他想知道在前$n$个人中(即前$n$个斐波那契数)上有多少对夫妇存在,使上述所有条件成立。
输入
输入的第一行代表测试数据的数量。每个数据由每行有一个整数 $1\leq n\leq 10^5$ .
输出
对于每组数据,打印出完美夫妇的数量。
样例输入 复制
6
1
4
8
17
20
25
样例输出 复制
0
3
5
11
13
17