Mức Góp Để Đạt Mục Tiêu

Minh muốn lập một kế hoạch đầu tư có kỷ luật để sau ~n~ tháng đạt được một mục tiêu tài chính cụ thể, chẳng hạn như quỹ học tập, tiền mua xe hoặc khoản dự phòng dài hạn.

Minh đã có sẵn ~P~ đồng. Mỗi tháng, khoản tiền hiện có sẽ tăng trưởng với lãi suất ~r~ basis points, sau đó Minh nộp thêm một khoản cố định ~C~ đồng vào cuối tháng.

Để thử xem với từng mục tiêu thì mình cần góp bao nhiêu mỗi tháng, Minh thường dùng công cụ Behivest Tools - Goal Based Contribution. Trong bài này, bạn cần tự tính ra đáp án.

Cho ~P, X, r, n~, hãy tìm giá trị nguyên nhỏ nhất của ~C~ sao cho sau đúng ~n~ tháng, số dư đạt ít nhất ~X~ đồng.

Quy tắc cập nhật mỗi tháng:

~A = \left\lfloor A \times \frac{10000 + r}{10000} \right\rfloor + C~

Nếu ngay từ đầu ~P \ge X~, đáp án là ~0~. Nếu ~n = 0~ mà ~P < X~, in ra -1.

Input

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

Mỗi test gồm 4 số nguyên ~P, X, r, n~:

• ~0 \le P \le 10^{12}~
• ~1 \le X \le 10^{18}~
• ~0 \le r \le 2000~
• ~0 \le n \le 2 \cdot 10^5~

Giới hạn thêm: tổng ~n~ của mọi test không vượt quá ~2 \cdot 10^5~.

Dữ liệu đảm bảo đáp án luôn nằm trong kiểu số nguyên 64-bit có dấu.

Output

Với mỗi test, in ra giá trị nhỏ nhất của ~C~, hoặc -1 nếu không thể.

Ví dụ

Input

4
1000000 5000000 50 12
5000000 5000000 123 24
500000 1000000 0 5
0 1 0 0

Output

319267
0
100000
-1