ゲームにっき(仮)正整数 $n$ に対して，$f(n)$ を $n$ を割り切る素数の和で定義する． $n$ を $f(n)$ に置き換えていく手順を繰り返すといずれ $n$ は素数になる． $n$ から始めた時，素数になるまでに必要な手順の数 $+1$ を $g(n)$ とする． $P$ 個のテストケースが与えられる． 各テストケースでは $A \leq n \leq B$ かつ $g(n) = K$ を満たす $n$ の個数を求める． $1 \leq P \leq 10^5$ $2 \leq A \leq B \leq 10^6$ $1 \leq K \leq 10^6$ $g(n)$ の最大値は $12$ 程度なので，$1\leq K \leq 12$ に対して，$g(n)=K$ となる $x$ 以下の $n$ の数を前計算しておく． $f(n)$ の値は篩っぽく求めて，$n > f(n)$ なので，
