Ami có một dãy số nguyên dương liên tiếp từ \(l\) đến \(r\). LN lại cho Ami hai số \(t\) và \(k\). Cần đếm xem có bao nhiêu số nguyên \(x\) thoả mãn:

1. \(l \le x \le r\)
2. \(x^t\) có đúng \(k\) chữ số \(0\) tận cùng

Input

• Dòng đầu tiên chứa số nguyên dương \(Q\) (\(Q \le 300\, 000\)) - số lượng test.
• \(n\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương \(l,r,t,k\) (\(l,r,t,k \le 10^{17}\)).

Output

• Ứng với mỗi bộ dữ liệu, in ra kết quả của bài toán.

1
1 110 2 2

10