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 将在第六天完成他的旅程。