1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4  5 const int size = 1000010; 6 int prime[size/10]; 7 bool vis[size]; 8 int tree[size]; 9 10 int lowBit( int x )11 {12     return x & (-x);13 }14 15 void update( int x , int var )16 {17     while( x<size )18     {19         tree[x] += var;20         x += lowBit(x);21     }22 }23 24 int getSum( int x )25 {26     int ans = 0;27     while( x )28     {29         ans += tree[x];30         x -= lowBit(x);31     }32     return ans;33 }34 35 bool solve( int x )36 {37     int sum = 0;38     while( x )39     {40         sum += x%10;41         x /= 10;42     }    43     if( vis[sum] )44         return true;45     return false;46 }47 48 void init( )49 {50     int cnt = 0;51     memset( vis , true , sizeof(vis) );52     memset( tree , 0 , sizeof(tree) );53     vis[1] = true;54     for( int i = 2 ; i<size ; ++i )55     {56         if( vis[i] )57         {58             prime[cnt++] = i;59             int j = i + i;60             while( j<size )61             {62                 vis[j] = false;63                 j += i;64             }            65         }66     }67     for( int i = 0 ; i<cnt ; ++i )68     {69         if( solve( prime[i] ) )70         {71             update( prime[i] , 1 );72         }73     }74 }75 76 int main()77 {78     cin.sync_with_stdio(false);79     int t , ans , L , R;80     init();81     cin >> t;82     for( int k = 1 ; k<=t ; ++k )83     {84         cin >> L >> R;85         ans = getSum(R) - getSum(L-1);86         cout << "Case #" << k << ": " << ans << endl;87     }88     return 0;89 }