Hoàn Thành Quỹ Khẩn Cấp

Sau khi biết mình cần kiểm soát chi tiêu tốt hơn, Lan đặt mục tiêu xây một quỹ khẩn cấp đủ dùng trong nhiều tháng nếu có biến cố bất ngờ như mất việc, ốm đau hoặc phát sinh chi phí lớn.

Lan đọc rằng một nguyên tắc phổ biến là nên chuẩn bị quỹ khẩn cấp bằng ~k~ tháng chi tiêu thiết yếu. Để thử nhanh các mức mục tiêu khác nhau, Lan còn dùng công cụ Behivest Tools - Emergency Fund Planner.

Hiện tại, mỗi tháng Lan cần ~E~ đồng cho các nhu cầu thiết yếu. Mục tiêu của Lan là có quỹ khẩn cấp bằng đúng ~k~ tháng chi tiêu thiết yếu, tức là ~E \times k~ đồng.

Lan đã có sẵn ~S~ đồng trong quỹ và mỗi tháng sẽ để thêm ~C~ đồng vào quỹ.

Hãy tính số tháng nhỏ nhất để Lan đạt hoặc vượt mục tiêu. Nếu không thể đạt được, in ra -1.

Input

Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 10^5)~.

Mỗi test gồm 4 số nguyên ~E, k, S, C~:

• ~1 \le E \le 10^{12}~
• ~0 \le k \le 24~
• ~0 \le S \le 10^{15}~
• ~0 \le C \le 10^{12}~

Output

Với mỗi test, in ra số tháng nhỏ nhất để đạt mục tiêu, hoặc -1 nếu không thể.

Ví dụ

Input

4
5000000 6 10000000 3000000
3000000 6 18000000 0
4000000 3 2000000 0
1 1 0 1

Output

7
0
-1
1