题目描述

在新年这个欢腾的 $vibe$ 之中，依然有一群孤单的人，而质数恰好又是公认的“孤单”的数字。

现有一排 $n$ 个人，每个人手中拿着一个数字 $a_i$ ，每个人的“孤单值”是 $1\sim a_i$ 中与 $a_i$ 互质的数字的个数。

现有 $q$ 个分组的派对方案，每组方案选取 $l,r$ 的范围，每组方案的评分是区间内“孤单值”为质数的人数。求问第几个分组方案评分最高。

输入格式

第一行， $1$ 个正整数 $n$ 。

第二行， $n$ 个正整数 $a_i$ 。

第三行， $1$ 个正整数 $q$ 。

接下来 $q$ 行，每行 $2$ 个正整数 $l_i,r_i$ ，表示当前方案的范围。

$1$ 个正整数，在 $1\sim q$ 之间，表示评分最大的方案序号（有相同最大评分的输出最靠前的序号）。

$3$ 人的“孤单值”分别为 $[2,1,0]$ ，在 $2$ 组方案中，第一组前两人的孤单值为质数的有 $1$ 人；第二组后两人的孤单值为质数的有 $0$ 人。因此第 $1$ 组方案评分最多。

对于 $60\%$ 的数据， $n\le 10^3,q\le 10^3$
对于 $100\%$ 的数据，$1\le n\le 10^5, 1\le a_i\le 10^9,1\le q \le 10^5,1\le l_i\le r_i\le n$