Một số nguyên chia hết cho 3 nếu tổng các chữ số của nó chia hết cho 3. Ví dụ, 3702 chia hết cho 3 và  12 (3+7+0+2) chia hết cho 3. Tính chất này vẫn giữ nguyên với các số chia hết cho 9

Ta cần đếm xem có bao nhiêu số nguyên có tính chất này

Input

Dòng đầu tiên gồm một số nguyên, số bộ test (T<=200)

Mỗi trường hợp sau gồm 3 số nguyên dương A, B và K (1<=A<=B<=2^31) và 0<K<10000)

Output

Vỡi mỗi trường hợp, đưa ra số các số nguyên trong đoạn [A,B] chia hết cho K và tổng các chữ số của chúng cũng chia hết cho K