stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;



const int N=2100,mod=924844033;

int n,K,cnt[N];

LL fac[N<<1],inv[N<<1],f[2][N],Ans;



LL qpow(LL x,int y)

{

	LL ret=1;

	while(y)

	{

		if(y&1) ret=ret*x%mod;

		x=x*x%mod, y>>=1;

	}

	return ret;

}



LL C(int x,int y)

{

	if(y>x) return 0;

	return fac[x]*inv[y]%mod*inv[x-y]%mod;

}



int main()

{

	scanf("%d%d",&n,&K);

	fac[0]=1;

	for(int i=1;i<=n<<1;++i) fac[i]=fac[i-1]*i%mod;

	inv[n<<1]=qpow(fac[n<<1],mod-2);

	for(int i=(n<<1)-1;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod;

	if(K*2>=n)

	{

		Ans=fac[n];

		for(int i=1;i<=(n-K)*2;++i)

			if(i&1) (Ans-=fac[n-i]*C((n-K)*2,i))%=mod;

			else (Ans+=fac[n-i]*C((n-K)*2,i))%=mod;

		(Ans+=mod)%=mod;

		printf("%lld",Ans); return 0;

	}

	for(int i=1;i<=K;++i) cnt[i]=(n-i-K)/(2*K)+1 + (n-i)/(2*K);

	f[0][0]=1;

	for(int i=1;i<=K;++i)

	{

		for(int j=0;j<=n;++j) f[1][j]=f[0][j];

		for(int j=0;j<=n;++j)

			for(int k=1;k<=min(j,cnt[i]);++k)

				(f[1][j]+=f[0][j-k]*C(cnt[i]-k+1,k)%mod)%=mod;

		for(int j=0;j<=n;++j) f[0][j]=f[1][j];

		for(int j=0;j<=n;++j)

			for(int k=1;k<=min(j,cnt[i]);++k)

				(f[0][j]+=f[1][j-k]*C(cnt[i]-k+1,k)%mod)%=mod;

	}

	Ans=fac[n];

	for(int i=1;i<=n;++i)

		if(i&1) (Ans-=f[0][i]*fac[n-i]%mod)%=mod;

		else (Ans+=f[0][i]*fac[n-i]%mod)%=mod;

	Ans=(Ans+mod)%mod;

	printf("%lld",Ans);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.146175788120118x):
#include<cstdio>

#define N 2002

#define p 924844033

inline int mod(int x){return x<p?x:x-p;}

int a[N],f[N][2],i,j,m,n,s,x;

int main()

{

	scanf("%d%d",&n,&m),f[0][0]=1;

	for(i=1;i<=m;i++)

	{

		for(j=0;j<=n;f[j++][0]=0)f[j][1]=mod(f[j][0]+f[j][1]);

		for(s=(n-i)/m+2>>1;s--;)

		for(j=n;j--;)

		{

			f[j+1][0]=mod(f[j+1][0]+f[j][0]);

			f[j+1][1]=mod(f[j+1][1]+mod(f[j][0]+f[j][1]));

			f[j][0]=mod(f[j][0]+f[j][1]);

			f[j][1]=0;

		}

		if(~((n-i)/m)&1)for(j=0;j<=n;j++)f[j][1]=0;

	}

	for(;i<=n&&i<=m<<1;i++)

	{

		for(j=0;j<=n;f[j++][1]=0)f[j][0]=mod(f[j][0]+f[j][1]);

		for(s=(n-i)/m+2>>1;s--;)

		for(j=n;j--;)

		{

			f[j+1][0]=mod(f[j+1][0]+f[j][0]);

			f[j+1][1]=mod(f[j+1][1]+mod(f[j][0]+f[j][1]));

			f[j][0]=mod(f[j][0]+f[j][1]);

			f[j][1]=0;

		}

		if(~((n-i)/m)&1)for(j=0;j<=n;j++)f[j][1]=0;

	}

	for(i=*a=1;i<=n;i++)a[i]=(long long)a[i-1]*i%p;

	for(i=0;i<=n;i++)x=i&1?(x+(long long)(p-a[n-i])*(f[i][0]+f[i][1]))%p:(x+(long long)a[n-i]*(f[i][0]+f[i][1]))%p;

	return 0&printf("%d\n",x);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define M 2010

#define MOD 924844033

#define rep(i, x, y) for(int i = (x); i <= (y); i ++)

inline int read() {

	char ch = getchar(); int x = 0, f = 1;

	while(ch < '0' || ch > '9') {

		if(ch == '-') f = -1;

		ch = getchar();

	} while('0' <= ch && ch <= '9') {

		x = x * 10 + ch - '0';

		ch = getchar();

	} return x * f;

}

bool vis[2010][2];

int f[4010][2010][2];

bool a[4010];

int fac[4010];

int sum;

int main() {

	int n = read(), k = read();

	fac[0] = 1; rep(i, 1, n) fac[i] = 1ll * i * fac[i - 1] % MOD;

	rep(i, 1, n) rep(j, 0, 1) if(!vis[i][j]) {

		int u = i, v = j;

		int now = 0;

		while(u <= n) {

			vis[u][v] = 1;

			u += k; v ^= 1;

			now ++;

		} a[sum += now] = 1;

	} f[1][0][0] = 1;

	rep(i, 2, sum) rep(j, 0, n) {

		(f[i][j][0] += f[i - 1][j][0]) %= MOD;

		(f[i][j][0] += f[i - 1][j][1]) %= MOD;

		if(!a[i - 1]) {

			(f[i][j][1] += f[i - 1][j - 1][0]) %= MOD;

		}

	} int ans = 0;

	rep(i, 0, n) {

		ans = (ans + 1ll * (i & 1 ? -1 : 1) * fac[n - i] * (f[sum][i][0] + f[sum][i][1]) % MOD + MOD) % MOD;

	} cout << ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.2249202653896614x):
#include <algorithm>

#include <cstdio>

#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)

using namespace std;



const int MOD = 924844033;

const int MAXN = 2000 + 5;



int N, K;

int fact[MAXN];



int cnt;

bool vis[MAXN][2], visCnt[MAXN * 2];



int DP[MAXN * 2][MAXN][2];



void prepare()

{

	fact[0] = 1;

	for (int i = 1; i < MAXN; i++)

		fact[i] = 1LL * fact[i - 1] * i % MOD;

}



int main()

{

	//REDIRECT("captain");



	scanf("%d%d", &N, &K);

	prepare();



	for (int i = 1; i <= N; i++)

		for (int j = 0; j < 2; j++)

		{

			if (vis[i][j])

				continue;



			int a = i, b = j;

			while (a <= N)

				cnt++, vis[a][b] = true, a += K, b = b ^ 1;



			visCnt[cnt] = true;

		}



	DP[1][0][0] = 1;

	for (int i = 1; i <= cnt; i++)

		for (int j = 0; j <= N; j++)

		{

			DP[i + 1][j][0] = (DP[i][j][0] + DP[i][j][1]) % MOD;

			if (!visCnt[i])

				DP[i + 1][j + 1][1] = DP[i][j][0];

		}



	int signum = 1, answer = 0;

	for (int i = 0; i <= N; i++)

	{

		answer = (answer

				+ ((((1LL * signum * (DP[cnt][i][0] + DP[cnt][i][1]) % MOD)

						+ MOD) % MOD) * fact[N - i] % MOD)) % MOD;

		signum = -signum;

	}



	printf("%d\n", answer);



	CLOSEALL();

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define M 2010

#define MOD 924844033

#define rep(i, x, y) for(int i = (x); i <= (y); i ++)

inline int read() {

	char ch = getchar(); int x = 0, f = 1;

	while(ch < '0' || ch > '9') {

		if(ch == '-') f = -1;

		ch = getchar();

	} while('0' <= ch && ch <= '9') {

		x = x * 10 + ch - '0';

		ch = getchar();

	} return x * f;

}

bool vis[2010][2];

int f[4010][2010][2];

bool a[4010];

int fac[4010];

int sum;

int main() {

	int n = read(), k = read();

	fac[0] = 1; rep(i, 1, n) fac[i] = 1ll * i * fac[i - 1] % MOD;

	rep(i, 1, n) rep(j, 0, 1) if(!vis[i][j]) {

		int u = i, v = j;

		int now = 0;

		while(u <= n) {

			vis[u][v] = 1;

			u += k; v ^= 1;

			now ++;

		} a[sum += now] = 1;

	} f[1][0][0] = 1;

	rep(i, 2, sum) rep(j, 0, n) {

		(f[i][j][0] += f[i - 1][j][0]) %= MOD;

		(f[i][j][0] += f[i - 1][j][1]) %= MOD;

		if(!a[i - 1]) {

			(f[i][j][1] += f[i - 1][j - 1][0]) %= MOD;

		}

	} int ans = 0;

	rep(i, 0, n) {

		ans = (ans + 1ll * (i & 1 ? -1 : 1) * fac[n - i] * (f[sum][i][0] + f[sum][i][1]) % MOD + MOD) % MOD;

	} cout << ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.9168737548500676x):
#include <cstdio>



const int MOD = 924844033;

const int MAXN = 2000;



inline int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}

inline int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}

inline int mul(int x, int y) {return 1LL * x * y % MOD;}



int fct[MAXN + 5];

int f[2][2][MAXN + 5], h[2][2][MAXN + 5], g[MAXN + 5], t;

void init() {

	fct[0] = 1;

	for(int i=1;i<=MAXN;i++)

		fct[i] = mul(fct[i-1], i);

	g[t = 0] = 1;

}



void insert(int m) {

	for(int i=0;i<=t;i++)

		f[0][0][i] = f[0][1][i] = f[1][1][i] = 0, f[1][0][i] = g[i];

	for(int i=1;i<=m;i++) {

		for(int j=0;j<=t;j++)

			for(int p=0;p<=1;p++)

				for(int q=0;q<=1;q++)

					h[p][q][j] = f[p][q][j], f[p][q][j] = 0;

		t++, f[0][0][t] = f[0][1][t] = f[1][0][t] = f[1][1][t] = 0;

		for(int j=0;j<=t;j++)

			for(int p=0;p<=1;p++)

				for(int q=0;q<=1;q++) {

					f[q][0][j] = add(f[q][0][j], h[p][q][j]);

					if( p == 0 ) {

						f[q][0][j+1] = sub(f[q][0][j+1], h[p][q][j]);

						f[q][1][j+1] = sub(f[q][1][j+1], h[p][q][j]);

					}

					else f[q][1][j+1] = sub(f[q][1][j+1], h[p][q][j]);

				}

	}

	for(int i=0;i<=t;i++) g[i] = add(f[0][0][i], f[1][0][i]);

}



int a[MAXN + 5], N, K;

int main() {

	init(), scanf("%d%d", &N, &K);

	for(int i=1;i<=N;i++) a[i % K]++;

	for(int i=0;i<K;i++) insert(a[i]);

	int ans = 0;

	for(int i=0;i<=N;i++)

		ans = add(ans, mul(fct[N-i], g[i]));

	printf("%d\n", ans);

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define RI register int

typedef long long LL;



using namespace std;



LL const mod = 924844033, MAXN = 1e4 + 5;

int vis[MAXN], len[MAXN], tot;

LL dp[2][MAXN][2], g[2][MAXN], frac[MAXN];

vector <LL> f[MAXN];



int main() {

 // freopen("count.in", "r", stdin);

 // freopen("count.out", "w", stdout);

  int n, k; scanf("%d %d", &n, &k);

  frac[0] = 1;

  for (RI i = 1; i <= n; ++i) frac[i] = frac[i - 1] * 1ll * i % mod;

  if (!k) return printf("%lld\n", frac[n]), 0;

  for (RI i = 1; i <= n; ++i)

    if (!vis[i]) {

      len[++tot] = 0;

      for (RI j = i; j <= n; j += k)

        vis[j] = 1, ++len[tot];

      memset(dp, 0, sizeof(dp));

      dp[1][0][0] = 1;

      for (RI j = 2; j <= len[tot]; ++j) {

        for (RI l = 0; l <= j >> 1; ++l) {

          dp[j & 1][l][0] = (dp[(j + 1) & 1][l][0] + dp[(j + 1) & 1][l][1]) % mod;

          if (l > 0) dp[j & 1][l][1] = dp[(j + 1) & 1][l - 1][0];

        }

      }

      for (RI j = 0; j <= len[tot] >> 1; ++j)

        f[tot].push_back(dp[len[tot] & 1][j][0] + dp[len[tot] & 1][j][1]);

    }

  g[1][0] = 1;

  for (RI i = 2; i <= (tot << 1) + 1; ++i) {

    memset(g[i & 1], 0, sizeof(g[i & 1]));

    for (RI j = 0; j <= len[i >> 1] >> 1; ++j)

      for (RI k = j; k <= n; ++k)

        g[i & 1][k] = (g[i & 1][k] + g[(i + 1) & 1][k - j] * f[i >> 1][j] % mod) % mod;

  }

  LL ans = 0;

  for (RI i = 0; i <= n; ++i)

    ans = (ans + (i & 1 ? -1ll : 1ll) * g[1][i] * frac[n - i] % mod) % mod;

  printf("%lld\n", (ans % mod + mod) % mod);

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.642499914403727x):
#include <bits/stdc++.h>

#define ll long long

using namespace std;

template<typename T>void read(T &x){

	x = 0;int f(1);char c = getchar();

	for(;!isdigit(c);c = getchar()) if(c == '-') f=-1;

	for(;isdigit(c);c = getchar()) x = x * 10 + c -'0';

	x *= f;

}

const ll p = 924844033;

int n,k;

ll inv[2005],jc[2005],invjc[2005];

ll dp[2005];

int line_size(int s){

	int tnum = (n-s) / (k<<1);

	int ret = tnum+1 <<1;

	if(s < k+1)	--ret;

	if(s+tnum*(k<<1)+k > n)	--ret;

	return ret;

}

ll c(int x,int y){return x > y?0:jc[y] * invjc[x] % p * invjc[y-x] % p;}

int main(){

	read(n);read(k);

	jc[0] = jc[1] = invjc[0] = invjc[1] = inv[1] = 1;

	for(int i(2);i<=n;++i){

		jc[i] = jc[i-1] * i % p;

		inv[i] = (p-p/i) * inv[p%i] % p;

		invjc[i] = invjc[i-1] * inv [i] % p;

	}

	dp[0] = 1;

	for(int s(1),asize(0);s<=min(n,k<<1);++s){

		int nsize = line_size(s); asize += ((n-s)/(k<<1)+1);

		for(int i = asize;i >= 0;--i)

			for(int j = i-1;j >= 0&&(i-j<=nsize-i+j+1);--j)

			dp[i] = (dp[i]+dp[j]*c(i-j,nsize-(i-j)+1))%p;

	}

	ll ans = 0;

	for(int i = 0,v = 1;i <= n;++i,v = -v)

		ans = (ans+v*dp[i]%p*jc[n-i]%p+p) %p;

	printf("%lld\n",ans);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define fo(i,a,b) for((i)=(a);i<=(b);i++)

#define rfo(i,a,b) for((i)=(a);i>=(b);i--)

#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))

#define ALL(vec) ((vec).begin(),(vec).end())

#define SOR(vec) sort(ALL(vec))

#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())

using namespace std;

int Q,L,R,v[100100],cnt[100100];

vector<int> pr;

void Linear(int nn){

	memset(v,0,sizeof(v));

	pr.clear();

	for(int i=2;i<=nn;i++){

		if(v[i]==0){v[i]=i,pr.push_back(i);}

		for(int j=0;j<pr.size();j++){

			if(pr[j]>v[i]||pr[j]>nn/i) break;

			v[i*pr[j]]=pr[j];

		}

	}

	for(int i=1;i<=nn;i++){

		cnt[i]=cnt[i-1];

		if((i%2==1))

			if((v[i]==i)&&(v[(i+1)/2]==((i+1)/2))) cnt[i]++;

	}

}

int main(){

	#ifdef FILIN

		#ifndef DavidDesktop

			freopen(FILIN,"r",stdin);

			freopen(FILOUT,"w",stdout);

		#endif

	#endif

	ios::sync_with_stdio(0);

	cin.tie(NULL);

	cout.tie(NULL);

	Linear(100000);

	cin>>Q;

	while(Q--){

		cin>>L>>R;

		cout<<cnt[R]-cnt[L-1]<<endl;

	}

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.7480319467445957x):
#include<iostream>

#include<cmath>

using namespace std;

bool isp[100100],is2017[100100];

int Prefix[100100];

int main()

{

	int N;

	cin>>N;

	for(int i=0;i<100100;i++)

		isp[i]=true;

	isp[0]=isp[1]=false;

	for(int i=2;i<=sqrt(100100);i++)

		if(isp[i])

			for(int j=i*i;j<100100;j+=i)

				isp[j]=false;

	for(int i=1;i<100100;i+=2)

		is2017[i]=(isp[i]&&isp[(i+1)/2]);

	for(int i=1;i<100100;i++)

		Prefix[i]=Prefix[i-1]+is2017[i];

	while(N--)

	{

		int L,R;

		cin>>L>>R;

		cout<<Prefix[R]-Prefix[L-1]<<endl;

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define fo(i,a,b) for((i)=(a);i<=(b);i++)

#define rfo(i,a,b) for((i)=(a);i>=(b);i--)

#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))

#define ALL(vec) ((vec).begin(),(vec).end())

#define SOR(vec) sort(ALL(vec))

#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())

using namespace std;

int Q,L,R,v[100100],cnt[100100];

vector<int> pr;

void Linear(int nn){

	memset(v,0,sizeof(v));

	pr.clear();

	for(int i=2;i<=nn;i++){

		if(v[i]==0){v[i]=i,pr.push_back(i);}

		for(int j=0;j<pr.size();j++){

			if(pr[j]>v[i]||pr[j]>nn/i) break;

			v[i*pr[j]]=pr[j];

		}

	}

	for(int i=1;i<=nn;i++){

		cnt[i]=cnt[i-1];

		if((i%2==1))

			if((v[i]==i)&&(v[(i+1)/2]==((i+1)/2))) cnt[i]++;

	}

}

int main(){

	#ifdef FILIN

		#ifndef DavidDesktop

			freopen(FILIN,"r",stdin);

			freopen(FILOUT,"w",stdout);

		#endif

	#endif

	ios::sync_with_stdio(0);

	cin.tie(NULL);

	cout.tie(NULL);

	Linear(100000);

	cin>>Q;

	while(Q--){

		cin>>L>>R;

		cout<<cnt[R]-cnt[L-1]<<endl;

	}

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.533165831843562x):
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

int q,presum[maxn];

bool isprime[maxn];

bool check(int x)

{

	return isprime[x]&&isprime[(x+1)/2];

}

void build()

{

	for(int i=2;i<maxn;i++)

		isprime[i]=true;

	for(int i=2;i<maxn;i++)

		if(isprime[i])

			for(int j=i+i;j<maxn;j+=i)

				isprime[j]=false;

	for(int i=2;i<maxn;i++)

		if(i&1)

			presum[i]=presum[i-1]+check(i);

		else

			presum[i]=presum[i-1];

}

void solve()

{

	int l,r;

	cin>>l>>r;

	cout<<presum[r]-presum[l-1]<<endl;

}

int main()

{

	ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

	cin>>q;

	build();

	while(q--)

		solve();

	return 0;

}

/*

1

3 7

output:2



4

13 13

7 11

7 11

2017 2017

output:

1

0

0

1 



6

1 53

13 91

37 55

19 51

73 91

13 49

output:

4

4

1

1

1

2



1

1 2

output:0



1

1 100000

output:672

*/
// Slower C++ solution:
#include<bits/stdc++.h>

#define fo(i,a,b) for((i)=(a);i<=(b);i++)

#define rfo(i,a,b) for((i)=(a);i>=(b);i--)

#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))

#define ALL(vec) ((vec).begin(),(vec).end())

#define SOR(vec) sort(ALL(vec))

#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())

using namespace std;

int Q,L,R,v[100100],cnt[100100];

vector<int> pr;

void Linear(int nn){

	memset(v,0,sizeof(v));

	pr.clear();

	for(int i=2;i<=nn;i++){

		if(v[i]==0){v[i]=i,pr.push_back(i);}

		for(int j=0;j<pr.size();j++){

			if(pr[j]>v[i]||pr[j]>nn/i) break;

			v[i*pr[j]]=pr[j];

		}

	}

	for(int i=1;i<=nn;i++){

		cnt[i]=cnt[i-1];

		if((i%2==1))

			if((v[i]==i)&&(v[(i+1)/2]==((i+1)/2))) cnt[i]++;

	}

}

int main(){

	#ifdef FILIN

		#ifndef DavidDesktop

			freopen(FILIN,"r",stdin);

			freopen(FILOUT,"w",stdout);

		#endif

	#endif

	ios::sync_with_stdio(0);

	cin.tie(NULL);

	cout.tie(NULL);

	Linear(100000);

	cin>>Q;

	while(Q--){

		cin>>L>>R;

		cout<<cnt[R]-cnt[L-1]<<endl;

	}

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.433982811142655x):
#include <iostream>

#include <sstream>

#include <fstream>

#include <string>

#include <vector>

#include <deque>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <algorithm>

#include <functional>

#include <utility>

#include <bitset>

#include <cmath>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <string.h>

#define rep(i,n) for(int i=0;i<n;i++)

#define forn(i,a,b) for(int i=a;i<=b;i++)

#define INF 2147483647

#define LLINF 9223372036854775807

using namespace std;

int l,r;

bool flag[100010];

int cnt[100010];

int main(){

	memset(cnt,0,sizeof(cnt));

	flag[0]=1;

	flag[1]=1;

	for(int i=2;i<=100000;i++){

		if(!flag[i]){

			for(int j=i+i;j<=100000;j+=i){

				flag[j]=1;

			}

		}

	}

	for(int i=2;i<=100000;i++){

		if(!flag[i]&&!flag[(i+1)/2]){

			cnt[i]=cnt[i-1]+1;

		}

		else cnt[i]=cnt[i-1];

	}

	int t;

	cin>>t;

	while(t--){

		int l,r;

		cin>>l>>r;

		cout<<cnt[r]-cnt[l-1]<<endl;

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int a,b,n;

vector<int> v;

bool prime[501010];

void SieveOfEratosthenes()

{

    int n=401010;



    memset(prime, true, sizeof(prime));



    for (int p=2; p*p<=n; p++)

    {

        if (prime[p] == true)

        {

            for (int i=p*2; i<=n; i += p)

                prime[i] = false;

        }

    }

    for (int p=3; p<=101010; p++)

    {

        if (prime[p] && prime[(p+1)/2])

        {

            v.push_back(p);

        }

    }

}

void init()

{

    SieveOfEratosthenes();

    /*cout<<v.size()<<endl;

    for(int i=0;i<v.size();i++)

    {

        cout<<v[i]<<endl;

    }*/

}

int bcount(int l,int r)

{

    std::vector<int>::iterator low,up;

    low=std::lower_bound (v.begin(), v.end(), l); //          ^

    up= std::upper_bound (v.begin(), v.end(), r); //                   ^

    return (up-v.begin())-(low-v.begin());

}

int main()

{

    init();

    int q,l,r;

    cin>>q;

    for(int i=0;i<q;i++)

    {

        cin>>l>>r;

        cout<<bcount(l,r)<<endl;

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.4827246344876799x):
#include<bits/stdc++.h>

using namespace std;

#define mx 100010

int a[mx],p[mx],k,koko[mx];



void sieve()

{

    a[1]=1;

    for(int i=2; i<sqrt(mx); i++)

    {

        if(!a[i])

        {

            p[k++]=i;

            for(int j=i*i; j<mx; j=j+i)

            {

                a[j]=1;

            }

        }

    }

}



int main()

{

    sieve();

    for(int i=2;i<mx;i++)

    {

        if(!a[i] && !a[(i+1)/2]) koko[i]=koko[i-1]+1;

        else koko[i]=koko[i-1];

    }

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int l,r;

        scanf("%d %d",&l,&r);

        printf("%d\n",koko[r]-koko[l-1]);

    }

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int a,b,n;

vector<int> v;

bool prime[501010];

void SieveOfEratosthenes()

{

    int n=401010;



    memset(prime, true, sizeof(prime));



    for (int p=2; p*p<=n; p++)

    {

        if (prime[p] == true)

        {

            for (int i=p*2; i<=n; i += p)

                prime[i] = false;

        }

    }

    for (int p=3; p<=101010; p++)

    {

        if (prime[p] && prime[(p+1)/2])

        {

            v.push_back(p);

        }

    }

}

void init()

{

    SieveOfEratosthenes();

    /*cout<<v.size()<<endl;

    for(int i=0;i<v.size();i++)

    {

        cout<<v[i]<<endl;

    }*/

}

int bcount(int l,int r)

{

    std::vector<int>::iterator low,up;

    low=std::lower_bound (v.begin(), v.end(), l); //          ^

    up= std::upper_bound (v.begin(), v.end(), r); //                   ^

    return (up-v.begin())-(low-v.begin());

}

int main()

{

    init();

    int q,l,r;

    cin>>q;

    for(int i=0;i<q;i++)

    {

        cin>>l>>r;

        cout<<bcount(l,r)<<endl;

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.4678921012744537x):
#include<bits/stdc++.h>

using namespace std;



#define ll      long long

#define MAX     100007

#define inf     99999999999999

#define MOD     1000000007

#define pii     pair<int,int>

#define FIN     freopen("input.txt","r",stdin);

#define FOUT    freopen("output.txt","w",stdout);



int nprime;

bool mark[MAX];



void sieve (void)

{

    long long i,j,lim=sqrt(MAX*1.0)+2;

    mark[0]=mark[1]=1;

    for(i=4;i<MAX;i+=2)

        mark[i]=1;

    for(i=3;i<=lim;i+=2)

    {

        if(!mark[i])

        {

            for(j=i*i;j<=MAX;j+=2*i)

                mark[j]=1;

        }

    }

}

ll q,l,r,res[MAX];

void pre()

{

    for(ll i=1;i<MAX;i+=2)

    {

        if(!mark[i] && !mark[(i+1)>>1])

        {

            res[i]++;

        }

    }

    for(ll i=1;i<MAX;i++)

    {

        res[i] += res[i-1];

    }

}

int main ()

{

    sieve();

    pre();

    scanf("%lld",&q);

    while(q--)

    {

        scanf("%lld %lld",&l,&r);

        printf("%lld\n",res[r]-res[l-1]);

    }

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int a,b,n;

vector<int> v;

bool prime[501010];

void SieveOfEratosthenes()

{

    int n=401010;



    memset(prime, true, sizeof(prime));



    for (int p=2; p*p<=n; p++)

    {

        if (prime[p] == true)

        {

            for (int i=p*2; i<=n; i += p)

                prime[i] = false;

        }

    }

    for (int p=3; p<=101010; p++)

    {

        if (prime[p] && prime[(p+1)/2])

        {

            v.push_back(p);

        }

    }

}

void init()

{

    SieveOfEratosthenes();

    /*cout<<v.size()<<endl;

    for(int i=0;i<v.size();i++)

    {

        cout<<v[i]<<endl;

    }*/

}

int bcount(int l,int r)

{

    std::vector<int>::iterator low,up;

    low=std::lower_bound (v.begin(), v.end(), l); //          ^

    up= std::upper_bound (v.begin(), v.end(), r); //                   ^

    return (up-v.begin())-(low-v.begin());

}

int main()

{

    init();

    int q,l,r;

    cin>>q;

    for(int i=0;i<q;i++)

    {

        cin>>l>>r;

        cout<<bcount(l,r)<<endl;

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.232273625069117x):
#include<bits/stdc++.h>

using namespace std;







int isPrime[100019], okay[100019], cum[100019];

void sieve()

{



    for(int i=2;i<=100009;i+=2)

        isPrime[i]=1;



     isPrime[2]=0;



    for(int i=3; i<=100009; i+=2)

    {

        if(isPrime[i]==0)

        {

            if(isPrime[(i+1)/2]==0)

                okay[i]=1;



            for(int j=2; i*j<=100009; j++)

            {

                isPrime[i*j]=1;

            }



        }

    }



    isPrime[1]=1;





//    for(int i=1; i<=10; i++)

//    {

//        if(okay[i]==1)

//        {

//            printf("%d\n",i);

//        }

//    }









    for(int i=3; i<=100009; i++)

    {

        cum[i]= cum[i-1]+okay[i];

       // printf("%d\n",cum[i]);

    }









}



int main()

{



    sieve();



    int q,l,r;

    scanf("%d",&q);





    while(q--)

    {

        scanf("%d %d",&l,&r);



        printf("%d\n",cum[r]-cum[l-1]);







    }





}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int a,b,n;

vector<int> v;

bool prime[501010];

void SieveOfEratosthenes()

{

    int n=401010;



    memset(prime, true, sizeof(prime));



    for (int p=2; p*p<=n; p++)

    {

        if (prime[p] == true)

        {

            for (int i=p*2; i<=n; i += p)

                prime[i] = false;

        }

    }

    for (int p=3; p<=101010; p++)

    {

        if (prime[p] && prime[(p+1)/2])

        {

            v.push_back(p);

        }

    }

}

void init()

{

    SieveOfEratosthenes();

    /*cout<<v.size()<<endl;

    for(int i=0;i<v.size();i++)

    {

        cout<<v[i]<<endl;

    }*/

}

int bcount(int l,int r)

{

    std::vector<int>::iterator low,up;

    low=std::lower_bound (v.begin(), v.end(), l); //          ^

    up= std::upper_bound (v.begin(), v.end(), r); //                   ^

    return (up-v.begin())-(low-v.begin());

}

int main()

{

    init();

    int q,l,r;

    cin>>q;

    for(int i=0;i<q;i++)

    {

        cin>>l>>r;

        cout<<bcount(l,r)<<endl;

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.3511061530851984x):
#include <iostream>

using namespace std;



const int MAXN = 1e5 + 10;

bool isp[MAXN];

int n, ps[MAXN];



int main() {

	isp[1] = 1;

	for (int i = 2; i < MAXN; i++)

		if (!isp[i])

			for (int j = i + i; j < MAXN; j += i)

				isp[j] = 1;

	for (int i = 2; i < MAXN; i++)

		if (!isp[i] && !isp[(i + 1) / 2])

			ps[i]++;

	for (int i = 1; i < MAXN; i++)

		ps[i] += ps[i - 1];

	cin >> n;

	for (int i = 0; i < n; i++) {

		int l, r;

		cin >> l >> r;

		cout << ps[r] - ps[l - 1] << '\n';

	}

}