CF1028H.Make Square

We call an array $b_1, b_2, \ldots, b_m$ good, if there exist two indices $i \lt j$ such that $b_i \cdot b_j$ is a perfect square.

Given an array $b_1, b_2, \ldots, b_m$, in one action you can perform one of the following:

• multiply any element $b_i$ by any prime $p$;
• divide any element $b_i$ by prime $p$, if $b_i$ is divisible by $p$.

Let $f(b_1, b_2, \ldots, b_m)$ be the minimum number of actions needed to make the array $b$ good.

You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$ and $q$ queries of the form $l_i, r_i$. For each query output $f(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i})$.

我们称一个数组 $b_1, b_2, \ldots, b_m$ 是“好的”，如果存在两个下标 $i \lt j$，使得 $b_i \cdot b_j$ 是一个完全平方数。

给定一个数组 $b_1, b_2, \ldots, b_m$，在一次操作中，你可以执行以下两种操作之一：

• 将任意元素 $b_i$ 乘以任意一个质数 $p$；
• 若 $b_i$ 能被质数 $p$ 整除，则可将 $b_i$ 除以质数 $p$。

令 $f(b_1, b_2, \ldots, b_m)$ 表示使数组 $b$ 变为“好的”所需的最少操作次数。

现给你一个包含 $n$ 个整数的数组 $a_1, a_2, \ldots, a_n$，以及 $q$ 个形如 $l_i, r_i$ 的查询。对每个查询，请输出 $f(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i})$。

The first line contains two integers $n$ and $q$ ($2 \le n \le 194\,598$, $1 \le q \le 1\,049\,658$) — the length of the array and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 5\,032\,107$) — the elements of the array.

Each of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \lt r_i \le n$) — the parameters of a query.

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 194\,598$，$1 \le q \le 1\,049\,658$）—— 分别表示数组的长度和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 5\,032\,107$）—— 表示数组的元素。

接下来的 $q$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \lt r_i \le n$）—— 表示一次查询的参数。

Output $q$ lines — the answers for each query in the order they are given in the input.

输出 $q$ 行——按输入中给出的顺序，依次输出每个查询的答案。

In the first query of the first sample you can multiply second number by 7 to get 259 and multiply the third one by 37 to get 1036. Then $a_2 \cdot a_3 = 268\,324 = 518^2$.

In the second query subarray is already good because $a_4 \cdot a_6 = 24^2$.

In the third query you can divide 50 by 2 to get 25. Then $a_6 \cdot a_8 = 30^2$.

在第一个样例的第一个查询中，你可以将第二个数乘以 $7$ 得到 $259$，并将第三个数乘以 $37$ 得到 $1036$。此时 $a_2 \cdot a_3 = 268\,324 = 518^2$。

在第二个查询中，子数组本身已满足条件，因为 $a_4 \cdot a_6 = 24^2$。

在第三个查询中，你可以将 $50$ 除以 $2$ 得到 $25$。此时 $a_6 \cdot a_8 = 30^2$。