Trong khi Lê mua đồ trang trí thì Quý đi mua bánh sinh nhật. Sau khi dạo vòng quanh thành phố thì Quý đã tìm được một chiếc bánh ưng ý trong một cửa hàng. Tình cờ thay hôm nay cũng là ngày kỉ niệm 3 năm khai trương ở đây. Khách hàng nào mua bánh kèm với nến mà thoã mãn cả hai điều kiện sau thì sẽ được luôn tặng bánh (chỉ cần trả tiền nến):

• Tổng các chữ số của số lượng nến nằm trong khoảng từ \(L\) đến \(R\);
• Nếu xếp những cây nến đó thành các vòng tròn trên bánh, mỗi vòng tròn có đúng \(M\) cây nến cho đến khi không xếp được nữa thì còn dư đúng \(K\) cây nến để xếp ở giữa.

Hãy giúp Quý tìm số lượng nến ít nhất cần mua để có được khuyến mãi hoặc thông báo rằng cửa hàng đang lừa đảo vì không tồn tại cách mua.

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \leq t \leq 10\)) là số lượng trường hợp cần kiểm tra.
• Trong \(t\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(L\), \(R\), \(M\) và \(K\) (\(1 \leq L \leq R \leq 10^3\), \(0 \leq K < M \leq 10^3\)).

Output

• Ứng với mỗi trường hợp, in ra một số nguyên là số lượng nến ít nhất cần mua hoặc \(-1\) nếu không tồn tại cách mua.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(M = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(R = 1\).
• Subtask \(3\) (\(30\%\) số điểm): \(L = R\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
5 7 1 0
1 1 6 4
7 7 8 2
2 3 3 1
1 10 134 47

5
10
34
-1
181