cut

题目来源

CF 1516D

题目描述

给你一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，以及 $q$ 次询问。

每次询问给定一个区间 $[l, r]$， 我们要把 $a_l, a_{l+1}, …, a_r$ 划分成若干段，要求每一段中数字的 LCM（最小公倍数）等于这一段中数字的乘积。

对于每次询问，求出区间最少可以被划分成几段。

输入格式

第一行两个整数 $n,q$，表示序列长度和询问数。

第二行 $n$ 个整数表示 $a_1,a_2,...,a_n$。

接下来 $q$ 行，每行两个整数 $l,r$ 代表一次询问。

输出格式

对于每个询问，输出一行一个整数表示答案。

样例输入

6 3
2 3 10 7 5 14
1 6
2 4
3 5

样例输出

3
1
2

数据范围

对于 $100\%$ 的数据，保证 $1\leq n,q\leq 10^5, 1\leq a_i\leq 10^5, 1\leq l\leq r\leq n$。