#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_SEGT_CNT		131072									// セグメントツリーデータ数
#define D_VAL_MAX		100000									// 最大値

// 内部変数
static int si1SegT[D_SEGT_CNT * 2];								// セグメントツリー(素数リスト)

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpT, *szpFpA;
#endif

// ルート
int
fSqrt(
	int piVal					// <I> 値 1～
)
{
	int liVal;

	// 正方形(辺の２乗)を１ずつ削る
	for (liVal = 1; piVal > 0; liVal++) {
		piVal -= liVal * 2 + 1;
	}

	return liVal - 1;
}

// 素数チェック
int
fIsPrime(
	int piVal					// <I> 値
)
{
	int i;

	// 対象外チェック
	if (piVal < 2) {
		return -1;
	}

	// チェック上限
	int liLimit = fSqrt(piVal);

	// チェック
	for (i = 2; i <= liLimit; i++) {
		if (piVal % i == 0) {
			return -1;
		}
	}

	return 0;
}

// セグメントツリー - 親データセット
int
fSegTSetP(
)
{
	int i;

	// 親番号範囲
	int liPNo1 = D_SEGT_CNT / 2;
	int liPNo2 = D_SEGT_CNT - 1;

	// 作成
	while (liPNo1 > 0) {
		for (i = liPNo1; i <= liPNo2; i++) {

			// 子番号
			int liCNo1 = i * 2;
			int liCNo2 = liCNo1 + 1;

			// セット
			si1SegT[i] = si1SegT[liCNo1] + si1SegT[liCNo2];
		}

		// 次の親番号範囲
		liPNo2 = liPNo1 - 1;
		liPNo1 /= 2;
	}

	return 0;
}

// セグメントツリー - 取得
int
fSegTGet(
	int piNNo					// <I> 現在番号 1～
	, int piNowS				// <I> 現在範囲 - 開始 0～D_SEGT_CNT-1
	, int piNowE				// <I> 現在範囲 - 終了 0～D_SEGT_CNT-1
	, int piGetS				// <I> 取得範囲 - 開始 0～D_SEGT_CNT-1
	, int piGetE				// <I> 取得範囲 - 終了 0～D_SEGT_CNT-1
)
{
	// 内包チェック
	if (piGetS <= piNowS && piNowE <= piGetE) {
		return si1SegT[piNNo];
	}

	// 中間位置
	int liCenter = (piNowS + piNowE) / 2;

	int liRet = 0;

	// 左側
	if (piGetS <= liCenter) {
		liRet = fSegTGet(piNNo * 2, piNowS, liCenter, piGetS, piGetE);
	}

	// 右側
	if (piGetE >= liCenter + 1) {
		liRet += fSegTGet(piNNo * 2 + 1, liCenter + 1, piNowE, piGetS, piGetE);
	}

	return liRet;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i, liRet;
	char lc1Buf[1024], lc1Out[1024];

	// データ初期化
	memset(si1SegT, 0, sizeof(si1SegT));							// セグメントツリー(素数リスト)

	// テストファイルオープン
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpT = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#endif

	// セグメントツリー(素数リスト) - 子データセット
	for (i = 1; i <= D_VAL_MAX; i += 2) {

		// 素数チェック
		liRet = fIsPrime(i);
		if (liRet != 0) {
			continue;
		}

		// 素数チェック
		liRet = fIsPrime((i + 1) / 2);
		if (liRet != 0) {
			continue;
		}

		// セット
		si1SegT[D_SEGT_CNT + i] = 1;
	}

	// セグメントツリー(素数リスト) - 親データセット
	fSegTSetP();

	// クエリ数取得
	int liQCnt;
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
	sscanf(lc1Buf, "%d", &liQCnt);

	// クエリ数でループ
	for (i = 0; i < liQCnt; i++) {

		// 範囲取得
		int liSNo, liENo;
#ifdef D_TEST
		fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
		fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
		sscanf(lc1Buf, "%d%d", &liSNo, &liENo);

		// 対象の個数取得
		int liCnt = fSegTGet(1, 0, D_SEGT_CNT - 1, liSNo, liENo);

		// 結果セット
		sprintf(lc1Out, "%d\n", liCnt);

		// 結果表示
#ifdef D_TEST
		fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
		if (strcmp(lc1Buf, lc1Out)) {
			siRes = -1;
		}
#else
		printf("%s", lc1Out);
#endif
	}

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpT);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}



Measured memory_bytes: 1536