NGUỒN: PreVNOI Ⅸ (BẮC GIANG 2019)
Nước
ODD có các đồng xu mệnh giá sau
1, 3, 5, 10, 30, 50, 100, 300, 500, 1000, 3000, 5000, 10 000, 30 000\text{ và }50 000
à
đồng. Ngân hàng ban hành thêm một loại xu mới với mệnh giá
x
đồng. Để trả đúng
t
đồng, cần tối thiểu bao nhiêu đồng xu?
Dữ liệu vào:
Dòng đầu ghi số test
q\le 50
q
x, t\ (x\ne t)
Dữ liệu ra:
In ra
q
Ví dụ:
Dữ liệu vào:
4
4700 53
4700 9400
4700 9401
4700 30000
Dữ liệu ra:
Giới hạn và gợi ý:
25\%
x ≤ 20, t ≤ 20
25\%
x ≤ 10^5, t ≤ 10^5
25\%
x ≤ 5.10^7, t ≤ 5.10^7
25\%
x ≤ 2.10^9, t ≤ 2.10^9
