Tích Lũy Đầu Tư Định Kỳ

Nam bắt đầu đầu tư dài hạn ngay từ những tháng đầu đi làm. Mỗi cuối tháng, sau khi nhận lương và kiểm tra lại các khoản chi tiêu, Nam chuyển thêm một khoản cố định vào danh mục đầu tư của mình.

Để hiểu rõ hơn việc đầu tư định kỳ có thể tạo ra khác biệt lớn như thế nào theo thời gian, Nam thường thử nhiều kịch bản khác nhau bằng công cụ Behivest Tools - SIP Calculator. Tuy nhiên, trong ứng dụng mà Nam đang tự viết để theo dõi tài sản, số dư luôn được cập nhật theo đúng quy tắc dưới đây.

Gọi ~A~ là số tiền hiện có. Trong mỗi tháng:

1. Danh mục tăng trưởng trước: ~A = \left\lfloor A \times \frac{10000 + r}{10000} \right\rfloor~
2. Sau đó Nam mới nộp thêm ~C~ đồng vào tài khoản

Ban đầu Nam có ~P~ đồng. Hãy tính số tiền Nam có sau đúng ~n~ tháng.

Input

Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 2 \cdot 10^4)~ — số lượng test.

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

• ~0 \le P \le 10^{12}~ — số tiền ban đầu
• ~0 \le C \le 10^{12}~ — số tiền nộp thêm vào cuối mỗi tháng
• ~0 \le r \le 2000~ — lãi suất theo basis points mỗi tháng
• ~0 \le n \le 2 \cdot 10^5~ — số tháng đầu tư

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 cuối cùng không vượt quá ~10^{18}~.

Output

Với mỗi test, in ra số tiền Nam có sau ~n~ tháng.

Ví dụ

Input

3
1000000 500000 50 3
0 100000 0 5
500000 0 100 12

Output

2522587
500000
563409

Giải thích

• Test 1: mỗi tháng số dư tăng ~0.5\%~, sau đó mới nộp thêm ~500000~ đồng.
• Test 2: không có lãi, nên kết quả chỉ là tổng số tiền nộp thêm.
• Test 3: không nộp thêm tiền, chỉ có lãi kép trên số vốn ban đầu.