GONE - G-One Numbers

The War of Evil vs Good continues and Ra-One and G-One continue to be on respective sides.

After saving all the cities with Ra-One Numbers G-One realised that some cities whose population is a "G-One Number" can be easy target for Ra-One.

A G-One number is a number sum of whose digits is a prime number

For example 12 .. sum = 1+2 = 3 ... 3 is a prime number.

G-One wants to find out all the populations which can be g-One numbers....

Can You help him.?

You will be given the range of population and you have to tell him how many in this range are G-One Numbers.

Input

first line has number 'c' indicating the number of ranges.

'c' lines follow and contain two numbers ... 'f' and 't' inclusive.

Output

Print a single line per case giving the number of populations which are G-One numbers.

Example

```Input:
310 191 920 29Output:
445```

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 5e2+5;

string a, b;
int n;
int dp[12][100][2];

bool isPrime[MAXN];

void sieve(){
memset(isPrime, true, sizeof isPrime);
isPrime[0] = isPrime[1] = false;
for(int i = 2;i <= 1000; i++){
if(isPrime[i]){
for(int j = i*i;j <= 1000; j+=i)
isPrime[j] = false;
}
}
}

ll solve(string &s, int idx, ll sum, int isPrefixEqual){
if(dp[idx][sum][isPrefixEqual] != -1)
return dp[idx][sum][isPrefixEqual];
ll res = 0;
if(idx == n){
if(isPrime[sum])
res = 1;
}else{
if(isPrefixEqual){
for(int i = 0;i <= s[idx]-'0'; i++){
if(i == s[idx]-'0'){
res += solve(s, idx+1, sum + i, 1);
}else{
res += solve(s, idx+1, sum + i, 0);
}
}
}else{
for(int i = 0;i < 10; i++){
res += solve(s, idx+1, sum + i, 0);
}
}
}
dp[idx][sum][isPrefixEqual] = res;
return res;
}

int f(string &a){
bool odd = true;
ll sum = 0;
for(int i = (int)a.size()-1;i >= 0; i--){
sum += a[i] - '0';
}
return (isPrime[sum]);
}

int main(){
io;
sieve();
int t;
cin >> t;
while(t--){
cin >> a >> b;
memset(dp, -1, sizeof dp);
n = b.size();
ll ansR = solve(b, 0, 0, 1);
memset(dp, -1, sizeof dp);
n = a.size();
ll ansL = solve(a, 0, 0, 1);
ll ans = ansR - ansL + f(a);
cout << ans << endl;
}
return 0;
}``````
Copy The Code &

Input

cmd
3
10 19
1 9
20 29

Output

cmd
4
4
5