Mua Đuốc

Bạn cần chế tạo $k$ ngọn đuốc. Mỗi ngọn đuốc cần đúng $1$ cây gậy và $1$ cục than. Ban đầu bạn có đúng $1$ cây gậy và không có cục than nào.

Bạn gặp một thương nhân có hai lựa chọn trao đổi:

• Đổi $1$ cây gậy lấy $x$ cây gậy (bạn mất $1$ cây gậy và nhận $x$ cây gậy).
• Đổi $y$ cây gậy lấy $1$ cục than (bạn mất $y$ cây gậy và nhận $1$ cục than).

Mỗi lần giao dịch chỉ được dùng một trong hai lựa chọn trên. Bạn có thể dùng mỗi lựa chọn bao nhiêu lần tuỳ ý, theo thứ tự tuỳ ý.

Hãy tìm số lần giao dịch tối thiểu cần thực hiện để có thể chế tạo ít nhất $k$ ngọn đuốc.

Có $t$ truy vấn độc lập, mỗi truy vấn cho bộ $(x,y,k)$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số truy vấn.
• Mỗi truy vấn chiếm một dòng gồm ba số nguyên $x$, $y$, $k$.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng số lần giao dịch tối thiểu.

Ràng buộc

• $1\le t\le 2·{10}^4$
• $2\le x\le {10}^9$
• $1\le y,k\le {10}^9$

Ví dụ