#1001. ODDCOIN - Tiền xu

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

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 dòng sau mỗi dòng ghi hai số x, t\ (x\ne t)

Dữ liệu ra:

In ra q dòng, mỗi dòng là kết quả một test

Ví dụ:

Dữ liệu vào:
4
4700 53
4700 9400 
4700 9401 
4700 30000
Dữ liệu ra:
2
2
3
1

Giới hạn và gợi ý:

  • 25\% số test có x ≤ 20, t ≤ 20
  • 25\% số test khác có x ≤ 10^5, t ≤ 10^5
  • 25\% số test khác có x ≤ 5.10^7, t ≤ 5.10^7
  • 25\% số test còn lại có x ≤ 2.10^9, t ≤ 2.10^9