/*
written by- Piyush Golani
language- c++
country- India
College- N.I.T Jamshedpur
*/
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<map>
#include<queue>
#include<cctype>
using namespace std;
#define pb push_back
#define all(s) s.begin(),s.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=a;i>=b;i--)
#define PI 3.1415926535897932384626433832795
#define INF 2000000000
#define BIG_INF 7000000000000000000LL
#define mp make_pair
#define eps 1e-9
#define LL long long
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007
#define mm 10000000
string inttostring(int n)
{
stringstream a;
a<<n;
return a.str();
}
int stringtoint(string A)
{
istringstream a(A);
int p;
a>>p;
return p;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
class TheDivisionGame {
public:
long long countWinningIntervals( int L, int R ) {
int n=R-L+1;
int cur[n],nim[n];
memset(nim,0,sizeof(nim));
f(i,L,R+1)
{
cur[i-L]=i;
}
for(int i=2;i*i<=R;i++)
{
int s=L;
if(L%i!=0)
s+=i-(s%i);
while(s<=R)
{
while(cur[s-L]%i==0)
{
cur[s-L]/=i;
nim[s-L]++;
}
s+=i;
}
}
f(i,0,n)
{
if(cur[i]>1) nim[i]++;
}
LL dp[32][2]={0},res=0;
for(int i=n-1;i>=0;i--)
{
f(x,0,32)
{
dp[x^nim[i]][i%2]=dp[x][!(i%2)];
}
dp[nim[i]][i%2]++;
res+=dp[0][i%2];
}
return ((LL)n*(n+1))/2-res;
}
};
// BEGIN CUT HERE
namespace moj_harness {
int run_test_case(int);
void run_test(int casenum = -1, bool quiet = false) {
if (casenum != -1) {
if (run_test_case(casenum) == -1 && !quiet) {
cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
}
return;
}
int correct = 0, total = 0;
for (int i=0;; ++i) {
int x = run_test_case(i);
if (x == -1) {
if (i >= 100) break;
continue;
}
correct += x;
++total;
}
if (total == 0) {
cerr << "No test cases run." << endl;
} else if (correct < total) {
cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
} else {
cerr << "All " << total << " tests passed!" << endl;
}
}
int verify_case(int casenum, const long long &expected, const long long &received, clock_t elapsed) {
cerr << "Example " << casenum << "... ";
string verdict;
vector<string> info;
char buf[100];
if (elapsed > CLOCKS_PER_SEC / 200) {
sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
info.push_back(buf);
}
if (expected == received) {
verdict = "PASSED";
} else {
verdict = "FAILED";
}
cerr << verdict;
if (!info.empty()) {
cerr << " (";
for (int i=0; i<(int)info.size(); ++i) {
if (i > 0) cerr << ", ";
cerr << info[i];
}
cerr << ")";
}
cerr << endl;
if (verdict == "FAILED") {
cerr << " Expected: " << expected << endl;
cerr << " Received: " << received << endl;
}
return verdict == "PASSED";
}
int run_test_case(int casenum__) {
switch (casenum__) {
case 0: {
int L = 9;
int R = 10;
long long expected__ = 2;
clock_t start__ = clock();
long long received__ = TheDivisionGame().countWinningIntervals(L, R);
return verify_case(casenum__, expected__, received__, clock()-start__);
}
case 1: {
int L = 2;
int R = 5;
long long expected__ = 9;
clock_t start__ = clock();
long long received__ = TheDivisionGame().countWinningIntervals(L, R);
return verify_case(casenum__, expected__, received__, clock()-start__);
}
case 2: {
int L = 2;
int R = 6;
long long expected__ = 13;
clock_t start__ = clock();
long long received__ = TheDivisionGame().countWinningIntervals(L, R);
return verify_case(casenum__, expected__, received__, clock()-start__);
}
case 3: {
int L = 2;
int R = 100;
long long expected__ = 4345;
clock_t start__ = clock();
long long received__ = TheDivisionGame().countWinningIntervals(L, R);
return verify_case(casenum__, expected__, received__, clock()-start__);
}
case 4: {
int L = 12566125;
int R = 12567777;
long long expected__ = 1313432;
clock_t start__ = clock();
long long received__ = TheDivisionGame().countWinningIntervals(L, R);
return verify_case(casenum__, expected__, received__, clock()-start__);
}
// custom cases
/* case 5: {
int L = ;
int R = ;
long long expected__ = ;
clock_t start__ = clock();
long long received__ = TheDivisionGame().countWinningIntervals(L, R);
return verify_case(casenum__, expected__, received__, clock()-start__);
}*/
/* case 6: {
int L = ;
int R = ;
long long expected__ = ;
clock_t start__ = clock();
long long received__ = TheDivisionGame().countWinningIntervals(L, R);
return verify_case(casenum__, expected__, received__, clock()-start__);
}*/
/* case 7: {
int L = ;
int R = ;
long long expected__ = ;
clock_t start__ = clock();
long long received__ = TheDivisionGame().countWinningIntervals(L, R);
return verify_case(casenum__, expected__, received__, clock()-start__);
}*/
default:
return -1;
}
}
}
int main(int argc, char *argv[]) {
if (argc == 1) {
moj_harness::run_test();
} else {
for (int i=1; i<argc; ++i)
moj_harness::run_test(atoi(argv[i]));
}
}
// END CUT HERE
LyoKd3JpdHRlbiBieS0gUGl5dXNoIEdvbGFuaQpsYW5ndWFnZS0gYysrCmNvdW50cnktIEluZGlhCkNvbGxlZ2UtIE4uSS5UIEphbXNoZWRwdXIKKi8KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxzc3RyZWFtPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPG1hcD4KI2luY2x1ZGU8cXVldWU+CiNpbmNsdWRlPGNjdHlwZT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBhbGwocykgcy5iZWdpbigpLHMuZW5kKCkKI2RlZmluZSBmKGksYSxiKSBmb3IoaW50IGk9YTtpPGI7aSsrKQojZGVmaW5lIEYoaSxhLGIpIGZvcihpbnQgaT1hO2k+PWI7aS0tKQojZGVmaW5lIFBJIDMuMTQxNTkyNjUzNTg5NzkzMjM4NDYyNjQzMzgzMjc5NQojZGVmaW5lIElORiAyMDAwMDAwMDAwCiNkZWZpbmUgQklHX0lORiA3MDAwMDAwMDAwMDAwMDAwMDAwTEwKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBlcHMgMWUtOQojZGVmaW5lIExMIGxvbmcgbG9uZwojZGVmaW5lIHNpKG4pIHNjYW5mKCIlZCIsJm4pCiNkZWZpbmUgc2xsKG4pIHNjYW5mKCIlbGxkIiwmbikKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwojZGVmaW5lIG1tIDEwMDAwMDAwCgpzdHJpbmcgaW50dG9zdHJpbmcoaW50IG4pCnsKICAgIHN0cmluZ3N0cmVhbSBhOwogICAgYTw8bjsKICAgIHJldHVybiBhLnN0cigpOwp9CgppbnQgc3RyaW5ndG9pbnQoc3RyaW5nIEEpCnsKICAgIGlzdHJpbmdzdHJlYW0gYShBKTsKICAgIGludCBwOwogICAgYT4+cDsKICAgIHJldHVybiBwOwp9CgovLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KCmNsYXNzIFRoZURpdmlzaW9uR2FtZSB7CnB1YmxpYzoKICAgbG9uZyBsb25nIGNvdW50V2lubmluZ0ludGVydmFscyggaW50IEwsIGludCBSICkgewogICAgaW50IG49Ui1MKzE7CiAgICBpbnQgY3VyW25dLG5pbVtuXTsKICAgIG1lbXNldChuaW0sMCxzaXplb2YobmltKSk7CiAgICBmKGksTCxSKzEpCiAgICB7CiAgICAgICAgY3VyW2ktTF09aTsKICAgIH0KICAgIGZvcihpbnQgaT0yO2kqaTw9UjtpKyspCiAgICB7CiAgICAgICAgaW50IHM9TDsKICAgICAgICBpZihMJWkhPTApCiAgICAgICAgcys9aS0ocyVpKTsKICAgICAgICB3aGlsZShzPD1SKQogICAgICAgIHsKICAgICAgICAgICAgd2hpbGUoY3VyW3MtTF0laT09MCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgY3VyW3MtTF0vPWk7CiAgICAgICAgICAgICAgICBuaW1bcy1MXSsrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHMrPWk7CiAgICAgICAgfQogICAgfQogICAgZihpLDAsbikKICAgIHsKICAgICAgICBpZihjdXJbaV0+MSkgbmltW2ldKys7CiAgICB9CiAgICBMTCBkcFszMl1bMl09ezB9LHJlcz0wOwogICAgZm9yKGludCBpPW4tMTtpPj0wO2ktLSkKICAgIHsKICAgICAgICBmKHgsMCwzMikKICAgICAgICB7CiAgICAgICAgICAgIGRwW3hebmltW2ldXVtpJTJdPWRwW3hdWyEoaSUyKV07CiAgICAgICAgfQogICAgICAgIGRwW25pbVtpXV1baSUyXSsrOwogICAgICAgIHJlcys9ZHBbMF1baSUyXTsKICAgIH0KICAgIHJldHVybiAoKExMKW4qKG4rMSkpLzItcmVzOwogICB9Cn07CgovLyBCRUdJTiBDVVQgSEVSRQpuYW1lc3BhY2UgbW9qX2hhcm5lc3MgewogICAgaW50IHJ1bl90ZXN0X2Nhc2UoaW50KTsKCXZvaWQgcnVuX3Rlc3QoaW50IGNhc2VudW0gPSAtMSwgYm9vbCBxdWlldCA9IGZhbHNlKSB7CgkJaWYgKGNhc2VudW0gIT0gLTEpIHsKCQkJaWYgKHJ1bl90ZXN0X2Nhc2UoY2FzZW51bSkgPT0gLTEgJiYgIXF1aWV0KSB7CgkJCQljZXJyIDw8ICJJbGxlZ2FsIGlucHV0ISBUZXN0IGNhc2UgIiA8PCBjYXNlbnVtIDw8ICIgZG9lcyBub3QgZXhpc3QuIiA8PCBlbmRsOwoJCQl9CgkJCXJldHVybjsKCQl9CgoJCWludCBjb3JyZWN0ID0gMCwgdG90YWwgPSAwOwoJCWZvciAoaW50IGk9MDs7ICsraSkgewoJCQlpbnQgeCA9IHJ1bl90ZXN0X2Nhc2UoaSk7CgkJCWlmICh4ID09IC0xKSB7CgkJCQlpZiAoaSA+PSAxMDApIGJyZWFrOwoJCQkJY29udGludWU7CgkJCX0KCQkJY29ycmVjdCArPSB4OwoJCQkrK3RvdGFsOwoJCX0KCgkJaWYgKHRvdGFsID09IDApIHsKCQkJY2VyciA8PCAiTm8gdGVzdCBjYXNlcyBydW4uIiA8PCBlbmRsOwoJCX0gZWxzZSBpZiAoY29ycmVjdCA8IHRvdGFsKSB7CgkJCWNlcnIgPDwgIlNvbWUgY2FzZXMgRkFJTEVEIChwYXNzZWQgIiA8PCBjb3JyZWN0IDw8ICIgb2YgIiA8PCB0b3RhbCA8PCAiKS4iIDw8IGVuZGw7CgkJfSBlbHNlIHsKCQkJY2VyciA8PCAiQWxsICIgPDwgdG90YWwgPDwgIiB0ZXN0cyBwYXNzZWQhIiA8PCBlbmRsOwoJCX0KCX0KCglpbnQgdmVyaWZ5X2Nhc2UoaW50IGNhc2VudW0sIGNvbnN0IGxvbmcgbG9uZyAmZXhwZWN0ZWQsIGNvbnN0IGxvbmcgbG9uZyAmcmVjZWl2ZWQsIGNsb2NrX3QgZWxhcHNlZCkgewoJCWNlcnIgPDwgIkV4YW1wbGUgIiA8PCBjYXNlbnVtIDw8ICIuLi4gIjsKCgkJc3RyaW5nIHZlcmRpY3Q7CgkJdmVjdG9yPHN0cmluZz4gaW5mbzsKCQljaGFyIGJ1ZlsxMDBdOwoKCQlpZiAoZWxhcHNlZCA+IENMT0NLU19QRVJfU0VDIC8gMjAwKSB7CgkJCXNwcmludGYoYnVmLCAidGltZSAlLjJmcyIsIGVsYXBzZWQgKiAoMS4wL0NMT0NLU19QRVJfU0VDKSk7CgkJCWluZm8ucHVzaF9iYWNrKGJ1Zik7CgkJfQoKCQlpZiAoZXhwZWN0ZWQgPT0gcmVjZWl2ZWQpIHsKCQkJdmVyZGljdCA9ICJQQVNTRUQiOwoJCX0gZWxzZSB7CgkJCXZlcmRpY3QgPSAiRkFJTEVEIjsKCQl9CgoJCWNlcnIgPDwgdmVyZGljdDsKCQlpZiAoIWluZm8uZW1wdHkoKSkgewoJCQljZXJyIDw8ICIgKCI7CgkJCWZvciAoaW50IGk9MDsgaTwoaW50KWluZm8uc2l6ZSgpOyArK2kpIHsKCQkJCWlmIChpID4gMCkgY2VyciA8PCAiLCAiOwoJCQkJY2VyciA8PCBpbmZvW2ldOwoJCQl9CgkJCWNlcnIgPDwgIikiOwoJCX0KCQljZXJyIDw8IGVuZGw7CgoJCWlmICh2ZXJkaWN0ID09ICJGQUlMRUQiKSB7CgkJCWNlcnIgPDwgIiAgICBFeHBlY3RlZDogIiA8PCBleHBlY3RlZCA8PCBlbmRsOwoJCQljZXJyIDw8ICIgICAgUmVjZWl2ZWQ6ICIgPDwgcmVjZWl2ZWQgPDwgZW5kbDsKCQl9CgoJCXJldHVybiB2ZXJkaWN0ID09ICJQQVNTRUQiOwoJfQoKCWludCBydW5fdGVzdF9jYXNlKGludCBjYXNlbnVtX18pIHsKCQlzd2l0Y2ggKGNhc2VudW1fXykgewoJCWNhc2UgMDogewoJCQlpbnQgTCAgICAgICAgICAgICAgICAgICAgID0gOTsKCQkJaW50IFIgICAgICAgICAgICAgICAgICAgICA9IDEwOwoJCQlsb25nIGxvbmcgZXhwZWN0ZWRfXyAgICAgID0gMjsKCgkJCWNsb2NrX3Qgc3RhcnRfXyAgICAgICAgICAgPSBjbG9jaygpOwoJCQlsb25nIGxvbmcgcmVjZWl2ZWRfXyAgICAgID0gVGhlRGl2aXNpb25HYW1lKCkuY291bnRXaW5uaW5nSW50ZXJ2YWxzKEwsIFIpOwoJCQlyZXR1cm4gdmVyaWZ5X2Nhc2UoY2FzZW51bV9fLCBleHBlY3RlZF9fLCByZWNlaXZlZF9fLCBjbG9jaygpLXN0YXJ0X18pOwoJCX0KCQljYXNlIDE6IHsKCQkJaW50IEwgICAgICAgICAgICAgICAgICAgICA9IDI7CgkJCWludCBSICAgICAgICAgICAgICAgICAgICAgPSA1OwoJCQlsb25nIGxvbmcgZXhwZWN0ZWRfXyAgICAgID0gOTsKCgkJCWNsb2NrX3Qgc3RhcnRfXyAgICAgICAgICAgPSBjbG9jaygpOwoJCQlsb25nIGxvbmcgcmVjZWl2ZWRfXyAgICAgID0gVGhlRGl2aXNpb25HYW1lKCkuY291bnRXaW5uaW5nSW50ZXJ2YWxzKEwsIFIpOwoJCQlyZXR1cm4gdmVyaWZ5X2Nhc2UoY2FzZW51bV9fLCBleHBlY3RlZF9fLCByZWNlaXZlZF9fLCBjbG9jaygpLXN0YXJ0X18pOwoJCX0KCQljYXNlIDI6IHsKCQkJaW50IEwgICAgICAgICAgICAgICAgICAgICA9IDI7CgkJCWludCBSICAgICAgICAgICAgICAgICAgICAgPSA2OwoJCQlsb25nIGxvbmcgZXhwZWN0ZWRfXyAgICAgID0gMTM7CgoJCQljbG9ja190IHN0YXJ0X18gICAgICAgICAgID0gY2xvY2soKTsKCQkJbG9uZyBsb25nIHJlY2VpdmVkX18gICAgICA9IFRoZURpdmlzaW9uR2FtZSgpLmNvdW50V2lubmluZ0ludGVydmFscyhMLCBSKTsKCQkJcmV0dXJuIHZlcmlmeV9jYXNlKGNhc2VudW1fXywgZXhwZWN0ZWRfXywgcmVjZWl2ZWRfXywgY2xvY2soKS1zdGFydF9fKTsKCQl9CgkJY2FzZSAzOiB7CgkJCWludCBMICAgICAgICAgICAgICAgICAgICAgPSAyOwoJCQlpbnQgUiAgICAgICAgICAgICAgICAgICAgID0gMTAwOwoJCQlsb25nIGxvbmcgZXhwZWN0ZWRfXyAgICAgID0gNDM0NTsKCgkJCWNsb2NrX3Qgc3RhcnRfXyAgICAgICAgICAgPSBjbG9jaygpOwoJCQlsb25nIGxvbmcgcmVjZWl2ZWRfXyAgICAgID0gVGhlRGl2aXNpb25HYW1lKCkuY291bnRXaW5uaW5nSW50ZXJ2YWxzKEwsIFIpOwoJCQlyZXR1cm4gdmVyaWZ5X2Nhc2UoY2FzZW51bV9fLCBleHBlY3RlZF9fLCByZWNlaXZlZF9fLCBjbG9jaygpLXN0YXJ0X18pOwoJCX0KCQljYXNlIDQ6IHsKCQkJaW50IEwgICAgICAgICAgICAgICAgICAgICA9IDEyNTY2MTI1OwoJCQlpbnQgUiAgICAgICAgICAgICAgICAgICAgID0gMTI1Njc3Nzc7CgkJCWxvbmcgbG9uZyBleHBlY3RlZF9fICAgICAgPSAxMzEzNDMyOwoKCQkJY2xvY2tfdCBzdGFydF9fICAgICAgICAgICA9IGNsb2NrKCk7CgkJCWxvbmcgbG9uZyByZWNlaXZlZF9fICAgICAgPSBUaGVEaXZpc2lvbkdhbWUoKS5jb3VudFdpbm5pbmdJbnRlcnZhbHMoTCwgUik7CgkJCXJldHVybiB2ZXJpZnlfY2FzZShjYXNlbnVtX18sIGV4cGVjdGVkX18sIHJlY2VpdmVkX18sIGNsb2NrKCktc3RhcnRfXyk7CgkJfQoKCQkvLyBjdXN0b20gY2FzZXMKCi8qICAgICAgY2FzZSA1OiB7CgkJCWludCBMICAgICAgICAgICAgICAgICAgICAgPSA7CgkJCWludCBSICAgICAgICAgICAgICAgICAgICAgPSA7CgkJCWxvbmcgbG9uZyBleHBlY3RlZF9fICAgICAgPSA7CgoJCQljbG9ja190IHN0YXJ0X18gICAgICAgICAgID0gY2xvY2soKTsKCQkJbG9uZyBsb25nIHJlY2VpdmVkX18gICAgICA9IFRoZURpdmlzaW9uR2FtZSgpLmNvdW50V2lubmluZ0ludGVydmFscyhMLCBSKTsKCQkJcmV0dXJuIHZlcmlmeV9jYXNlKGNhc2VudW1fXywgZXhwZWN0ZWRfXywgcmVjZWl2ZWRfXywgY2xvY2soKS1zdGFydF9fKTsKCQl9Ki8KLyogICAgICBjYXNlIDY6IHsKCQkJaW50IEwgICAgICAgICAgICAgICAgICAgICA9IDsKCQkJaW50IFIgICAgICAgICAgICAgICAgICAgICA9IDsKCQkJbG9uZyBsb25nIGV4cGVjdGVkX18gICAgICA9IDsKCgkJCWNsb2NrX3Qgc3RhcnRfXyAgICAgICAgICAgPSBjbG9jaygpOwoJCQlsb25nIGxvbmcgcmVjZWl2ZWRfXyAgICAgID0gVGhlRGl2aXNpb25HYW1lKCkuY291bnRXaW5uaW5nSW50ZXJ2YWxzKEwsIFIpOwoJCQlyZXR1cm4gdmVyaWZ5X2Nhc2UoY2FzZW51bV9fLCBleHBlY3RlZF9fLCByZWNlaXZlZF9fLCBjbG9jaygpLXN0YXJ0X18pOwoJCX0qLwovKiAgICAgIGNhc2UgNzogewoJCQlpbnQgTCAgICAgICAgICAgICAgICAgICAgID0gOwoJCQlpbnQgUiAgICAgICAgICAgICAgICAgICAgID0gOwoJCQlsb25nIGxvbmcgZXhwZWN0ZWRfXyAgICAgID0gOwoKCQkJY2xvY2tfdCBzdGFydF9fICAgICAgICAgICA9IGNsb2NrKCk7CgkJCWxvbmcgbG9uZyByZWNlaXZlZF9fICAgICAgPSBUaGVEaXZpc2lvbkdhbWUoKS5jb3VudFdpbm5pbmdJbnRlcnZhbHMoTCwgUik7CgkJCXJldHVybiB2ZXJpZnlfY2FzZShjYXNlbnVtX18sIGV4cGVjdGVkX18sIHJlY2VpdmVkX18sIGNsb2NrKCktc3RhcnRfXyk7CgkJfSovCgkJZGVmYXVsdDoKCQkJcmV0dXJuIC0xOwoJCX0KCX0KfQoKCmludCBtYWluKGludCBhcmdjLCBjaGFyICphcmd2W10pIHsKCWlmIChhcmdjID09IDEpIHsKCQltb2pfaGFybmVzczo6cnVuX3Rlc3QoKTsKCX0gZWxzZSB7CgkJZm9yIChpbnQgaT0xOyBpPGFyZ2M7ICsraSkKCQkJbW9qX2hhcm5lc3M6OnJ1bl90ZXN0KGF0b2koYXJndltpXSkpOwoJfQp9Ci8vIEVORCBDVVQgSEVSRQo=