#algo #ruby

red_john_is_back.rb

# 4xN wall
# Infinite supply of 1x4 and 4x1 bricks
# M - total number of ways in which the bricks can be arranged on the wall
# P - answer - number of prime numbers up to M

# Input
# T - integer
# T lines of one integer

# Output
# T lines containing P for each test case

require 'prime'

def num_primes_upto m
  count = 0
  2.upto(m) do |num|
      count += 1 if Prime.prime? num
  end
  count
end

def solution n, memo
  return 1 if n == 1
  return 1 if n == 0
  return 0 if n < 0
  return memo[n] ? memo[n] : solution(n-1,memo) + solution(n-4,memo)
end

def solve n
  memo = Array.new(n)
  solution(n, memo)
end

t = $stdin.readline.chomp.to_i
t.times do
  n = $stdin.readline.chomp.to_i
  m = solve(n)
  puts num_primes_upto m
end