Ngân hàng Picu

Trong một buổi quan sát thiên văn, FullHouse Dev đã phát hiện ra một hành tinh mới với hệ thống tài chính độc đáo. Họ quyết định mô phỏng lại hệ thống này bằng một bài toán thú vị về Ngân hàng Picu.

Bài toán

FullHouse Dev có \(S\) đô la và muốn gửi vào Ngân hàng Picu. Ngân hàng này có cách tính lãi đặc biệt:

• Mỗi tháng, ngân hàng thêm \(N\) đô la vào tài khoản trong \(M\) tháng đầu tiên.
• Đúng vào tháng thứ \(M\), ngân hàng thêm \(K\) đô la vào tài khoản.
• Kịch bản này lặp lại theo chu kỳ (tức là tháng thứ \(M+1\) lại thêm \(N\) đô la, và cứ thế).

Nhiệm vụ của FullHouse Dev là tính xem cần bao nhiêu tháng để số tiền trong tài khoản đạt ít nhất \(X\) đô la.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Mỗi test case gồm 5 số nguyên \(S\), \(N\), \(M\), \(K\), và \(X\) như mô tả trong bài toán.

OUTPUT FORMAT:

• Với mỗi test case, in ra số tháng tối thiểu cần thiết để đạt được ít nhất \(X\) đô la trong tài khoản.

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq S, N, M, K, X \leq 10^9\)

Ví dụ

INPUT

2
2 5 4 3 51
2 5 4 3 46

OUTPUT

11
10

Giải thích

• Trong test case đầu tiên, FullHouse Dev cần 11 tháng để đạt được ít nhất 51 đô la.
• Trong test case thứ hai, họ cần 10 tháng để đạt được ít nhất 46 đô la.

FullHouse Dev nhận ra rằng việc tính toán lãi suất phức tạp này cũng giống như việc dự đoán quỹ đạo của các thiên thể trong vũ trụ. Họ quyết định áp dụng kiến thức về chu kỳ và quỹ đạo thiên văn vào việc giải quyết bài toán này.