Vinh làm việc cho một công ty chuyên lập trình điều khiển các cây ATM. Nhiệm vụ của Vinh là phải lập trình điều khiển cây ATM sao cho mỗi lần nhận lệnh rút một lượng tiền trị giá W đồng thì cây ATM sẽ đưa ra một số N ít nhất tờ tiền sao cho tổng giá trị bằng W. Biết rằng trong cây ATM có các loại tiền mệnh giá 1000, 2000, 3000, 5000, 1000·10¹ , 2000·10¹ , 3000·10¹ , 5000·10¹ , . . . , 1000·10^c , 2000·10^c , 3000·10^c , 5000·10^c với c là một số nguyên dương, và số lượng tờ tiền mỗi loại là không hạn chế.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên dương T là số lượng test (T ≤ 1000).
Mỗi dòng trong số T dòng tiếp theo là dữ liệu cho từng test bao gồm hai số nguyên dương W và c với W ≤ 10¹⁸ và c ≤ 15.

Kết quả

Kết quả tương ứng với mỗi test được viết trên một dòng duy nhất bao gồm 2 số nguyên dương N và S, trong đó S là số lượng các cách rút ra số N ít nhất các tờ tiền. Ghi ra số 0 nếu như không có cách rút.