w4R6i8 - Online Java Compiler & Debugging Tool

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0){
		    long l=sc.nextLong();
		    long r=sc.nextLong();
		    int mod=sc.nextInt();
		    int k=sc.nextInt();
		    System.out.println(solve(r,mod,k)-solve(l-1,mod,k));
		}
	}
	public static int solve(long num,int mod,int k){
	    int [][][] dp=new int[19][mod][10];  //---> 10^18 so 19
        for (int i=0;i<=9;i++){
            dp[1][i%mod][i]=1;
        }
        for (int i=2;i<=18;i++){
            for (int j=0;j<mod;j++){
                for (int m=0;m<=9;m++){
                    int rem=(j-m)%mod;
                    if(rem<0)rem+=mod;
                    for (int l=0;l<=9;l++) {
                        dp[i][j][m]+=dp[i-1][rem][l];
                    }
                }
            }
        }
	    int cnt=0;
	    String s=String.valueOf(num);
	    for (int i=1;i<s.length();i++){
            for (int j=1;j<=9;j++){
                cnt+=dp[i][k][j];
            }
        }
        int [] d=new int[s.length()];
        for(int i=0;i<s.length();i++){
            d[i]=s.charAt(i)-'0';
	    }
	    int psum=0;
	    int len=s.length();
        for (int i=0;i<len;i++){
            int dig=s.charAt(i)-'0';
            int rem=len-i;
            int start = (i == 0) ? 1 : 0;
            for (int j=start;j<dig;j++){
                int n=(k-psum)%mod;
                if (n<0)n+=mod;
                cnt+=dp[rem][n][j];
            }
            psum=(psum+dig)%mod;
        }
        if(psum%mod==k)cnt+=1;
        return cnt;
	}
}