#215420. [MCO 2025] GCD Equality

Evirir the dragon found positive integers . They want to answer queries of the form (), which means:

• Construct the array . In one operation, Evirir can choose two adjacent integers in , say and (), and replace them with one integer . What is the minimum number of operations needed to make all elements in equal?

Can you help them answer the queries fast?

Note: denotes the greatest common divisor (GCD) of integers and . For example, , , and . See https://en.wikipedia.org/wiki/Greatest_common_divisor

The first line contains two space-separated integers and (, ).

The second line contains space-separated integers ().

Each of the following lines contains two integers and (), representing a query.

For each query in order, output an integer (the answer) on a line.

样例输入 1

10 6
36 24 120 24 36 60 48 24 24 9
1 7
2 4
6 10
6 8
8 9
10 10

样例输出 1

4
1
4
2
0
0

Note

For the first query (), . One optimal solution is (chosen elements are , the new element from the last operation is ):

• :
• :
• :
• :

It can be proven that one cannot make all elements equal in fewer than 4 operations.

For the second query (), . One optimal solution is .

For the third and fourth query, one can keep merging until one element is left.

For the fifth and sixth query, all elements of are already equal.

Scoring

Subtask 1 ( points): , .

Subtask 2 ( points): .

Subtask 3 ( points): .

Subtask 4 ( points): For all , .

Subtask 5 ( points): For all , for some integer .

Subtask 6 ( points): . For all , the -th query is .

Subtask 7 ( points): For all , .

Subtask 8 ( points): No additional constraints.