Bạn An đang học Toán-ngón-tay, với tuyệt chiêu múa tay tính toán.

Bạn An đang cầm \(X\) viên sỏi đứng trước một dãy vô hạn các ô.
Ô thứ nhất, bạn An rải vào \(b\) viên sỏi.
Từ ô thứ hai trở đi, ô thứ sau sẽ được rải nhiều hơn ô phía trước \(a\) viên sỏi.

Đố các bạn và bạn An, viên sỏi cuối cùng sẽ nằm ở ô số mấy?

À, để làm khó các bạn, thì câu hỏi trên sẽ được hỏi \(t\) lần: giả sử ta thay đổi \(a\), \(b\) và \(X\) trong bài toán trên, thì kết quả tương ứng là bao nhiêu?

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(t\) \((t \leq 10^5)\), là số lượng câu hỏi.
• \(t\) dòng tiếp theo, từ dòng \(2\) tới dòng \(t+1\), mỗi dòng lần lượt chứa ba số \(a\), \(b\) và \(X\) \((1 \leq a, b \leq 100; X \leq 10^9)\).

Định dạng đầu ra

• In ra \(t\) dòng, dòng thứ \(i\) tương ứng với đáp án của câu hỏi ở dòng \(i+1\) của đầu vào.

Điểm số

• Subtask \(1\) (\(40\%\) số điểm): \(t=1\)
• Subtask \(2\) (\(10\%\) số điểm): \(a = 2; b=1\)
• Subtask \(3\) (\(20\%\) số điểm): cả \(t\) câu hỏi đều có cùng một cặp số \(a\) và \(b\)
• Subtask \(4\) (\(30\%\) số điểm): không có giới hạn gì thêm

Ví dụ

1
2 3 10

3

2
2 3 10
1 1 12

3
5