Mạnh SadBoy là một chàng trai nổi tiếng trong câu lạc bộ lập trình Programming Lab của IUH. Anh ta đam mê lập trình từ nhỏ và ước mơ trở thành một Dev Game.

Nhân ngày 14/2 này, Mạnh đã viết ra một con game tặng cho H để cô ấy có thể chơi game này giải trí lúc không có Mạnh bên cạnh.

Game khá đơn giản, trong game người chơi phải điều khiển nhân vật của mình đi farm lính (hạ gục lính) để có tiền, sau khi có tiền nhân vật sẽ có thể mua các thuốc tăng sức mạnh (sức mạnh đầu game của nhân vật là ~0~). Và khi có chỉ số sức mạnh đúng bằng ~N~ thì người chơi có thể hạ gục được trùm cuối và qua màn tiếp theo. Khi hạ gục được ~1~ lính thì người chơi sẽ có được ~1~ vàng và trong cửa hàng có bán ~4~ loại thuốc tăng cường sức mạnh như sau:

1. Loại ~1~: sẽ tăng sức mạnh hiện tại lên ~2~ lần và có giá là ~A~ vàng.
2. Loại ~2~: sẽ tăng sức mạnh hiện tại lên ~3~ lần và có giá là ~B~ vàng.
3. Loại ~3~: sẽ tăng sức mạnh hiện tại lên ~5~ lần và có giá là ~C~ vàng.
4. Loại ~4~: sẽ tăng thêm hoặc giảm bớt ~1~ sức mạnh của nhân vật và có giá là ~D~ vàng.

Để đảm bảo game không có bị bug gì và đảm bảo H không hack được game của Mạnh code ra, nên Mạnh đã nhờ bạn chơi thử game này trước và yêu cầu bạn mỗi lần chơi bạn hãy cho anh ấy biết số lính tối thiểu mà bạn cần phải đi farm để có thể vượt qua màn chơi tương ứng nhé.

Input

Dòng đầu tiên chứa sớ nguyên ~T~ là số màn chơi Mạnh cần nhờ bạn chơi thử (~ 1 \leq T \leq 10 ~).

~T~ dòng tiếp theo, mỗi dòng sẽ chứa ~4~ số nguyên ~N, A, B, C, D~ tương ứng (~1 \leq N \leq 10^{18}, 1 \leq A, B, C, D \leq 10^9~).

Output

Với mỗi màn chơi, bạn hãy in ra số lính tối thiểu cần phải hạ gục để có đủ lượng vàng nâng cấp sức mạnh và vượt qua màn game.

Sample Input

4
15 10 3 2 1
15 2 2 2 2
202 40 2 1 9
20240219 6 8 6 8

Sample Output

5
6
42
132

Giải thích

Ở trường hợp 1, cách để nhân vật có sức mạnh ~15~ như sau:

1. Đầu tiên, nhân vật sức mạnh là ~0~
2. Tăng sức mạnh của nhân vật lên ~1~ với ~1~ đồng khi thuốc loại ~4~
3. Tăng sức mạnh của nhân vật lên ~2~ với ~1~ đồng khi thuốc loại ~4~
4. Tăng sức mạnh của nhân vật lên ~3~ với ~1~ đồng khi thuốc loại ~4~
5. Tăng sức mạnh của nhân vật lên ~15~ với ~2~ đồng khi thuốc loại ~3~

Như vậy cần có ít nhất là ~5~ vàng.

SubTask

• SubTask 1: 40 điểm với testcase có ~N \leq 10~
• SubTask 2: 60 điểm với testcase có ~N \leq 10^{18}~