Algorithm


Problem link- https://www.spoj.com/problems/GONE/

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:
3
10 19
1 9
20 29

Output: 4
4
5

 

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 & Try With Live Editor

Input

x
+
cmd
3
10 19
1 9
20 29

Output

x
+
cmd
4
4
5
Advertisements

Demonstration


SPOJ Solution-G-One Numbers-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python