Problem D

//============================================================================
// Name        : ACM
// Author      : Tarango Khan
// Copyright   : Team Byteheads
// Description : !!!Hello World!!!
//============================================================================

#include <bits/stdc++.h>
using namespace std;
#define Size 150005
#define Max 150005

string int2str(long long a) {
    stringstream ss;
    ss << a;
    string str = ss.str();
    return str;
}

long long DP[18][2][165][1460];
int N;
string num;
long long st,ed;

bool RelativelyPrime (long long a, long long b) {
    if(a == 0 || b == 0) return false;
    for (;;) {
        if (!(a %= b)) return b == 1;
        if (!(b %= a)) return a == 1;
    }
    return 0;
}

long long call(int cur,int dgt_sum,int sqr_sum,bool f){
    if(cur == N){
        if(RelativelyPrime(dgt_sum,sqr_sum) == true) return 1;
        return 0;
    }
    if(DP[cur][f][dgt_sum][sqr_sum] != -1)  return DP[cur][f][dgt_sum][sqr_sum];
    long long res = 0;
    int add1 = 0,add2 = 0;
    if(f == true){
        for(char ch = '0';ch<=num[cur];ch++){
            int dgt = (int)(ch - '0');
            add1 = dgt,add2 = dgt*dgt;
            if(ch == num[cur]){
                res = res + call(cur+1,(dgt_sum+add1),(sqr_sum+add2),true);
            }else{
                res = res + call(cur+1,(dgt_sum+add1),(sqr_sum+add2),false);
            }
        }
    }else{
        for(char ch = '0';ch<='9';ch++){
            int dgt = (int)(ch - '0');
            add1 = dgt,add2 = dgt*dgt;
            res = res + call(cur+1,(dgt_sum+add1),(sqr_sum+add2),false);
        }
    }
    return DP[cur][f][dgt_sum][sqr_sum] = res;
}

int main() {
    int nCase;
    scanf("%d",&nCase);
    for(int cs = 1;cs<=nCase;cs++){
        scanf("%lld %lld",&st,&ed);
        memset(DP,-1,sizeof(DP));
        num = int2str(ed);
        N = num.length();
        long long res1 = call(0,0,0,true);

        memset(DP,-1,sizeof(DP));
        num = int2str(st-1);
        N = num.length();
        long long res2 = call(0,0,0,true);
        printf("%lld\n",res1-res2);
    }
    return 0;
}