!http://web.agr.ehime-u.ac.jp/~kishou/Lecture/atmosphere/Fortran90/Chap4_answer.pdf
!-----------------------------------------
! エラトステネスのふるい
implicit none
logical, dimension(100000) :: flag ! ここでは論理型を使ったが、整数型でも可
integer, dimension(100000) :: count=0, nitakazu_count=0, ruiseki_count=0
integer :: i, n, nn, a, b
flag(:) = .false. ! すべて「偽」に初期化
n = 0 ! 素数の個数を数えるカウンター
do i = 2, 100000
    if (flag(i)) cycle ! 「偽」すなわち素数でなければ次の数へ
    count(i)=1
    if ( count(int((i+1)/2))==1 ) then
        nitakazu_count(i)=1
    endif
    !write(6,*) i ! 出力して
    n = n + 1 ! カウンタをひとつ増やし
    flag(i:100000:i) = .true. ! その倍数をすべて「真」にする
enddo

!nitakazu_count(2)=0

!write(6,*) nitakazu_count

do i = 2, 99999
  ruiseki_count(i+1)=ruiseki_count(i)+nitakazu_count(i+1)
enddo

read(5,*) nn
do i= 1, nn
  read(5,*) a, b
  write(6,*) ruiseki_count(b)-ruiseki_count(a-1)
  
enddo

stop
end
