So Sánh Hai Kế Hoạch Đầu Tư

Hà đang cân nhắc giữa hai kế hoạch đầu tư khác nhau. Chỉ nhìn vào lãi suất là chưa đủ, vì mỗi kế hoạch còn có thể khác nhau ở vốn ban đầu, số tiền góp thêm hàng tháng và phí duy trì định kỳ.

Để so sánh khách quan hơn, Hà thường thử nhiều kịch bản trên công cụ Behivest Tools - Investment Comparison. Trong bài này, bạn cần mô phỏng chính xác hai kế hoạch theo quy tắc được mô tả.

Với mỗi tháng của một kế hoạch:

1. Số dư tăng trưởng: ~A = \left\lfloor A \times \frac{10000 + r}{10000} \right\rfloor~
2. Nộp thêm ~C~ đồng
3. Trừ phí cố định ~F~ đồng. Nếu số dư âm thì xem như bằng ~0~

Cho hai kế hoạch:

• Kế hoạch A: ~P_A, C_A, r_A, F_A~
• Kế hoạch B: ~P_B, C_B, r_B, F_B~

Hãy tìm tháng nhỏ nhất ~m~ ~(0 \le m \le n)~ sao cho sau đúng ~m~ tháng, giá trị kế hoạch A không nhỏ hơn kế hoạch B. Nếu điều đó không xảy ra trong ~n~ tháng, in ra -1.

Input

Dòng đầu tiên chứa số nguyên ~T~.

Mỗi test gồm 9 số nguyên:

~P_A, C_A, r_A, F_A, P_B, C_B, r_B, F_B, n~

Trong đó:

• ~0 \le P_A, P_B \le 10^{12}~
• ~0 \le C_A, C_B \le 10^{12}~
• ~0 \le r_A, r_B \le 2000~
• ~0 \le F_A, F_B \le 10^{12}~
• ~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 mọi giá trị phát sinh trong quá trình mô phỏng không vượt quá ~10^{18}~.

Output

Với mỗi test, in ra tháng nhỏ nhất thỏa mãn điều kiện, hoặc -1.

Ví dụ

Input

4
1000000 120000 40 0 1200000 70000 30 0 12
0 100000 100 0 0 100000 100 0 0
1000 0 0 0 2000 0 0 0 12
0 1000 0 0 100 0 0 0 10

Output

4
0
-1
1