← 返回题目列表

Codeforces · 2060/A

A. 斐波那契数列

中文机器翻译题面 查看原题

有一个 $$$5$$$ 整数数组。最初,您只知道 $$$a_1,a_2,a_4,a_5$$$。您可以将 $$$a_3$$$ 设置为任何正整数、负整数或零。数组的斐波那契数是满足 $$$a_{i+2}=a_i+a_{i+1}$$$ 的整数 $$$i$$$ ($$$1 \leq i \leq 3$$$) 的数量。求 $$$a_3$$$ 的所有整数值的最大斐波那契数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。

每个测试用例的唯一行包含四个整数 $$$a_1, a_2, a_4, a_5$$$ ($$$1 \leq a_i \leq 100$$$)。

输出

对于每个测试用例,在新行中输出最大斐波那契数。

示例

输入 #1

6
1 1 3 5
1 3 2 1
8 10 28 100
100 1 100 1
1 100 1 100
100 100 100 100

输出 #1

3
2
2
1
1
2

注意

在第一个测试用例中,我们可以将 $$$a_3$$$ 设置为 $$$2$$$ 以实现 $$$3$$$ 的最大斐波那契数。

在第三个测试用例中,可以证明 $$$2$$$ 是可以实现的最大斐波那契数。这可以通过将 $$$a_3$$$ 设置为 $$$18$$$ 来完成。