You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

旅程

kirep决定开启一段漫长的徒步旅行。

他计划第一天走 a 千米，第二天走 b 千米，第三天走 c 千米，第四天和第一天一样走 a 千米，第五天和第二天一样走 b 千米，第六天和第三天一样走 c 千米，依此类推。

当kirep累计行走至少 n 千米时，他就会结束旅程。你的任务是确定kirep将在哪一天完成旅程。

输入

第一行包含一个整数 t（1 ≤ t ≤ 10⁴）—— 测试用例的数量。

每个测试用例占一行，包含四个整数 n、a、b、c（1 ≤ n ≤ 10⁹；1 ≤ a, b, c ≤ 1e2）。

输出

对于每个测试用例，输出一个整数，表示kirep累计行走至少 n 千米并完成旅程的那一天。

示例

输入

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

输出

5
1
6
1000000000