func countSemiPrimes(n int, p, q []int) []int {
	primes := make([]bool, n+1)
	for i := range primes {
		primes[i] = true
	}
	semiPrimes := make([]int, n+1)
	result := make([]int, len(p))

	for i := 2; i*i <= n; i++ {
		if primes[i] {
			for k := i * i; k <= n; k += i {
				primes[k] = false
			}
		}
	}

	for k := 2; k*k <= n; k++ {
		if primes[k] {
			for i := 2; i*k <= n; i++ {
				if primes[i] {
					semiPrimes[k*i] = 1
				}
			}
		}
	}

	for i := 1; i <= n; i++ {
		semiPrimes[i] += semiPrimes[i-1]
	}

	for k := range p {
		result[k] = semiPrimes[q[k]] - semiPrimes[p[k]-1]
	}

	return result
}

import Control.Monad (forM_, when)
import Control.Monad.ST (runST)
import Data.Array (Array, listArray, (!))
import Data.Array.ST (newArray, readArray, runSTUArray, writeArray)
import Data.Array.Unboxed (UArray)

isPrimeArr :: Int -> UArray Int Bool
isPrimeArr n = runSTUArray $ do
  arr <- newArray (0, n) True
  forM_ [2 .. floor (sqrt (fromIntegral n :: Double))] $ \i -> do
    p <- readArray arr i
    when p $ forM_ [i * i, i * i + i .. n] $ \k -> writeArray arr k False
  return arr

semiPrimeArr :: Int -> UArray Int Bool -> UArray Int Bool
semiPrimeArr n primes = runSTUArray $ do
  arr <- newArray (0, n) False
  forM_ [k | k <- [2 .. floor (sqrt (fromIntegral n :: Double))], primes ! k] $ \k ->
    forM_ (takeWhile (\i -> i * k <= n) [2 ..]) $ \i ->
      when (primes ! i) $ writeArray arr (k * i) True
  return arr

prefixCounts :: Int -> UArray Int Bool -> Array Int Int
prefixCounts n semi =
  listArray (0, n) (scanl1 (+) (0 : [if semi ! i then 1 else 0 | i <- [1 .. n]]))

countSemiPrimes :: Int -> [Int] -> [Int] -> [Int]
countSemiPrimes n p q = [prefix ! qi - prefix ! (pi' - 1) | (pi', qi) <- zip p q]
  where
    primes = isPrimeArr n
    semi   = semiPrimeArr n primes
    prefix = prefixCounts n semi

import java.util.Arrays;

public class Solution {
    public static int[] countSemiPrimes(int n, int[] p, int[] q) {
        boolean[] primes = new boolean[n + 1];
        Arrays.fill(primes, true);
        int[] semiPrimes = new int[n + 1];
        int[] semiPrimeCounts = new int[p.length];

        for (int i = 2; (long) i * i <= n; i++) {
            if (primes[i]) {
                for (int k = i * i; k <= n; k += i) {
                    primes[k] = false;
                }
            }
        }

        for (int k = 2; (long) k * k <= n; k++) {
            if (primes[k]) {
                for (int i = 2; i * k <= n; i++) {
                    if (primes[i]) {
                        semiPrimes[k * i] = 1;
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            semiPrimes[i] += semiPrimes[i - 1];
        }

        for (int k = 0; k < p.length; k++) {
            semiPrimeCounts[k] = semiPrimes[q[k]] - semiPrimes[p[k] - 1];
        }

        return semiPrimeCounts;
    }
}

(defun count-semi-primes (n p q)
  (let ((primes (make-array (1+ n) :initial-element t))
        (semi-primes (make-array (1+ n) :initial-element 0)))
    (loop for i from 2 while (<= (* i i) n)
          do (when (aref primes i)
               (loop for k from (* i i) to n by i
                     do (setf (aref primes k) nil))))
    (loop for k from 2 while (<= (* k k) n)
          do (when (aref primes k)
               (loop for i from 2 while (<= (* i k) n)
                     do (when (aref primes i)
                          (setf (aref semi-primes (* k i)) 1)))))
    (loop for i from 1 to n
          do (incf (aref semi-primes i) (aref semi-primes (1- i))))
    (loop for v in p
          for qi in q
          collect (- (aref semi-primes qi) (aref semi-primes (1- v))))))

function countSemiPrimes(int $n, array $p, array $q): array
{
    $primes          = array_fill(0, $n + 1, true);
    $semiPrimes      = array_fill(0, $n + 1, 0);
    $semiPrimeCounts = array_fill(0, count($p), 0);

    for ($i = 2; $i * $i <= $n; $i++) {
        if ($primes[$i]) {
            for ($k = $i * $i; $k <= $n; $k += $i) {
                $primes[$k] = false;
            }
        }
    }

    for ($k = 2; $k * $k <= $n; $k++) {
        if ($primes[$k]) {
            for ($i = 2; $i * $k <= $n; $i++) {
                if ($primes[$i]) {
                    $semiPrimes[$k * $i] = 1;
                }
            }
        }
    }

    for ($i = 1; $i <= $n; $i++) {
        $semiPrimes[$i] += $semiPrimes[$i - 1];
    }

    foreach ($p as $k => $v) {
        $semiPrimeCounts[$k] = $semiPrimes[$q[$k]] - $semiPrimes[$v - 1];

    }

    return $semiPrimeCounts;


}

def count_semi_primes(n: int, p: list[int], q: list[int]) -> list[int]:
    primes = [True] * (n + 1)
    semi_primes = [0] * (n + 1)

    i = 2
    while i * i <= n:
        if primes[i]:
            for k in range(i * i, n + 1, i):
                primes[k] = False
        i += 1

    k = 2
    while k * k <= n:
        if primes[k]:
            i = 2
            while i * k <= n:
                if primes[i]:
                    semi_primes[k * i] = 1
                i += 1
        k += 1

    for i in range(1, n + 1):
        semi_primes[i] += semi_primes[i - 1]

    return [semi_primes[q[idx]] - semi_primes[p[idx] - 1] for idx in range(len(p))]

fn count_semi_primes(n: usize, p: &[usize], q: &[usize]) -> Vec<i64> {
    let mut is_prime = vec![true; n + 1];
    let mut semi_primes = vec![0i64; n + 1];

    let mut i = 2;
    while i * i <= n {
        if is_prime[i] {
            let mut k = i * i;
            while k <= n {
                is_prime[k] = false;
                k += i;
            }
        }
        i += 1;
    }

    let mut k = 2;
    while k * k <= n {
        if is_prime[k] {
            let mut i = 2;
            while i * k <= n {
                if is_prime[i] {
                    semi_primes[k * i] = 1;
                }
                i += 1;
            }
        }
        k += 1;
    }

    for i in 1..=n {
        semi_primes[i] += semi_primes[i - 1];
    }

    p.iter()
        .zip(q.iter())
        .map(|(&pi, &qi)| semi_primes[qi] - semi_primes[pi - 1])
        .collect()
}

function countSemiPrimes(n: number, p: number[], q: number[]): number[] {
  const primes: boolean[] = new Array(n + 1).fill(true);
  const semiPrimes: number[] = new Array(n + 1).fill(0);
  const semiPrimeCounts: number[] = new Array(p.length).fill(0);

  for (let i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (let k = i * i; k <= n; k += i) {
        primes[k] = false;
      }
    }
  }

  for (let k = 2; k * k <= n; k++) {
    if (primes[k]) {
      for (let i = 2; i * k <= n; i++) {
        if (primes[i]) {
          semiPrimes[k * i] = 1;
        }
      }
    }
  }

  for (let i = 1; i <= n; i++) {
    semiPrimes[i] += semiPrimes[i - 1];
  }

  for (let k = 0; k < p.length; k++) {
    semiPrimeCounts[k] = semiPrimes[q[k]] - semiPrimes[p[k] - 1];
  }

  return semiPrimeCounts;
}

cyclic_rotation() {
    local -n _a="$1"
    local -n _out="$2"
    local _k=$3
    local _size=${#_a[@]}
    if (( _size == 0 )); then
        _out=()
        return
    fi
    _k=$(( _k % _size ))
    _out=()
    local _i
    for ((_i = 0; _i < _size; _i++)); do
        _out[(_i + _k) % _size]=${_a[_i]}
    done
}

#include <vector>

std::vector<int> cyclicRotation(std::vector<int> a, int k)
{
    if (!a.empty()) {
        for (int i = 0; i < k; ++i) {
            int back = a.back();
            a.pop_back();
            a.insert(a.begin(), back);
        }
    }

    return a;
}