Monocarp decided to embark on a long hiking journey.

He decided that on the first day he would walk $$$a$$$ kilometers, on the second day he would walk $$$b$$$ kilometers, on the third day he would walk $$$c$$$ kilometers, on the fourth day, just like on the first, he would walk $$$a$$$ kilometers, on the fifth day, just like on the second, he would walk $$$b$$$ kilometers, on the sixth day, just like on the third, he would walk $$$c$$$ kilometers, and so on.

Monocarp will complete his journey on the day when he has walked at least $$$n$$$ kilometers in total. Your task is to determine the day on which Monocarp will complete his journey.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one line containing four integers $$$n$$$, $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le a, b, c \le 10^6$$$).

Output

For each test case, output one integer — the day on which Monocarp will have walked at least $$$n$$$ kilometers in total and will complete his journey.

Note

In the first example, over the first four days, Monocarp will cover $$$1 + 5 + 3 + 1 = 10$$$ kilometers. On the fifth day, he will cover another $$$5$$$ kilometers, meaning that in total over five days he will have covered $$$10 + 5 = 15$$$ kilometers. Since $$$n = 12$$$, Monocarp will complete his journey on the fifth day.

In the second example, Monocarp will cover $$$6$$$ kilometers on the first day. Since $$$n = 6$$$, Monocarp will complete his journey on the very first day.

In the third example, Monocarp will cover $$$3 + 4 + 1 + 3 + 4 + 1 = 16$$$ kilometers over the first six days. Since $$$n = 16$$$, Monocarp will complete his journey on the sixth day.

Journey

Examples