来自暑假集训的第一场组队赛，当时很多队伍第一个过的就是这个题目。一看就是一个数位DP，因为恰恰好队伍里面三个人当时都不会数位DP，也是挺纠结的，都过了好长时间，队友才A掉，不过还是蛮佩服队友的，不会数位DP，纯粹凭着想象A掉的，还是挺强的。
我们用dp[i][j]记录枚举到第i位时，和为j的状态，进行DFS记忆化搜索，因为我们总共才16位数，所以每一位的和加起来最多也只能达到144，所以我们直接先预处理1~144之间的质数，用于判断。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2000+5;
typedef long long LL;
int bit[20];
int prime[40] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139};
LL dp[20][maxn];
int a[150];
LL dfs(int len, int sum,int ismax)
{if(len == -1) return a[sum];if(!ismax && dp[len][sum]!=-1) return dp[len][sum];LL ans = 0;int Max = ismax? bit[len]:9;for(int i=0; i<=Max; i++)ans += dfs(len-1, sum+i, ismax&&i==Max); return ismax? ans : dp[len][sum]=ans;
}
LL solve(LL n)
{int len = 0;while(n){bit[len++] = n%10;n /= 10;}LL ans = dfs(len-1, 0, 1);return ans;
}
int main()
{int T;scanf("%d", &T);for(int i=0; i<34; i++) a[prime[i]]++;memset(dp,-1,sizeof(dp));while(T--){LL L,R;cin >> L >> R;cout << solve(R)-solve(L-1) << endl;}return 0;
}