← 返回题目列表

Codeforces · 2051/B

B. 旅程

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

Monocarp决定踏上漫长的徒步旅行。

他决定第一天走$$$a$$$公里,第二天走$$$b$$$公里,第三天走$$$c$$$公里,第四天,和第一天一样,走$$$a$$$公里,第五天,和第二天一样,走$$$b$$$公里,第六天,和第五天一样。第三,他会步行 $$$c$$$ 公里,依此类推。

Monocarp 将在他总共行走至少 $$$n$$$ 公里的那一天完成他的旅程。你的任务是确定 Monocarp 完成旅程的日期。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由一行组成,其中包含四个整数 $$$n$$$、$$$a$$$、$$$b$$$、$$$c$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le a, b, c \le 10^6$$$)。

输出

对于每个测试用例,输出一个整数 - Monocarp 总计行走至少 $$$n$$$ 公里并完成旅程的那一天。

示例

输入 #1

4
12 1 5 3
6 6 7 4
16 3 4 1
1000000000 1 1 1

输出 #1

5
1
6
1000000000

注意

在第一个示例中,在前四天内,Monocarp 将覆盖 $$$1 + 5 + 3 + 1 = 10$$$ 公里。第五天,他将再行驶 $$$5$$$ 公里,这意味着在五天内他总共将行驶 $$$10 + 5 = 15$$$ 公里。由于 $$$n = 12$$$,Monocarp 将在第五天完成他的旅程。

在第二个示例中,Monocarp 将在第一天行驶 $$$6$$$ 公里。由于 $$$n = 6$$$,Monocarp 将在第一天完成他的旅程。

在第三个示例中,Monocarp 将在前六天内覆盖 $$$3 + 4 + 1 + 3 + 4 + 1 = 16$$$ 公里。由于 $$$n = 16$$$,Monocarp 将在第六天完成他的旅程。