Đóng gói sách

Bối cảnh

FullHouse Dev đang chuyển nhà và cần đóng gói bộ sưu tập sách ấn tượng của mình vào các hộp các-tông để chuyển đi.

Yêu cầu

FullHouse Dev có X kệ sách, mỗi kệ chứa đúng Y cuốn sách. Mỗi hộp các-tông có thể chứa tối đa Z cuốn sách. Để không làm xáo trộn việc sắp xếp sách, FullHouse Dev sẽ đảm bảo rằng sách từ các kệ khác nhau sẽ không được đặt trong cùng một hộp.

Với những điều kiện này, số lượng hộp tối thiểu cần thiết để đóng gói tất cả sách là bao nhiêu?

Input

• Dòng đầu tiên chứa số nguyên T — số lượng bộ test.
• Mỗi bộ test gồm một dòng chứa ba số nguyên cách nhau bởi dấu cách X, Y, và Z: các giá trị được mô tả trong đề bài.

Output

• Với mỗi bộ test, in ra trên một dòng mới một số nguyên: số lượng hộp tối thiểu cần thiết để đóng gói tất cả sách.

Ràng buộc

• 1 ≤ T ≤ 1000
• 1 ≤ X, Y, Z ≤ 1000

Ví dụ 1

Input

4
5 9 9
5 9 7
2 3 2
22 34 12

Output

5
10
4
66

Giải thích ví dụ

• Test 1: Mỗi hộp có thể chứa 9 cuốn sách, và mỗi kệ có 9 cuốn sách. Vì vậy, FullHouse Dev chỉ cần năm hộp: một hộp cho mỗi kệ.

• Test 2: Mỗi hộp có thể chứa 7 cuốn sách, và mỗi kệ có 9 cuốn sách. Vì vậy, FullHouse Dev cần hai hộp để chứa tất cả sách của một kệ (ví dụ, một hộp chứa 4 cuốn và hộp khác chứa 5 cuốn). Có năm kệ, nên tổng số hộp cần thiết là 5 × 2 = 10.

• Test 3: Mỗi hộp có thể chứa 2 cuốn sách, và mỗi kệ có 3 cuốn sách. Vì vậy, FullHouse Dev cần hai hộp để chứa tất cả sách của một kệ (ví dụ, một hộp chứa 2 cuốn và hộp khác chứa 1 cuốn). Có hai kệ, nên tổng số hộp cần thiết là 2 × 2 = 4.

• Test 4: Mỗi kệ cần 3 hộp để đóng gói tất cả sách. Có 22 kệ, nên câu trả lời là 22 × 3 = 66.

Thông tin học tập

• Buổi: B04
• Concepts: for/while loops, multiple test cases
• Giới hạn kiến thức: B01-B04
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 10