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?

Input

• 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)~

Giới hạn:

• ~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~

Output

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

Sample

Input #1

4
4700 53
4700 9400 
4700 9401 
4700 30000

Output #1

2
2
3
1

Problem source: PreVNOI Ⅸ (BẮC GIANG 2019)