$1 \le N \le 500$ なので、各駅からそのままシミュレーションすればいい。
ある駅 $i$ に時刻 $t$ に着いた時、次の駅に到着する時間は、
制約 $1 \le l,r \le 10^5$ なので、とりあえず $10^5$ までの「2017に似た数」をすべて求める。
$10^5$ までの素数をすべて求め、$\frac{10^5}{2}$ までの素数 $p$ について、$2p-1$ も素数ならば、$2p-1$ が「2017に似た数」である。
すべて求めたら、小さい順にソートしておく。各クエリの答えは、二分探索で求められる。
二分探索で、「$r_i$ が挿入される位置 ー $l_i$ が挿入される位置」が、答えとなる。ただし、
とする。これは、Python の bisect ライブラリでは、bisect_left()
とbisect()
で使い分けられる。