B"This time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array a of length n written on it, and then he does the following: Formally, he partitions the elements of a_l, a_{l + 1}, ldots, a_r into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for q independent ranges (l, r) , tell Baby Ehab the minimum number of subarrays he needs. The first line contains 2 integers n and q ( 1 <= n,q <= 10^5 ) -- the length of the array a and the number of queries. The next line contains n integers a_1 , a_2 , ldots , a_n ( 1 <= a_i <= 10^5 ) -- the elements of the array a . Each of the next q lines contains 2 integers l and r ( 1 <= l <= r <= n ) -- the endpoints of this query's interval. For each query, print its answer on a new line. The first query asks about the whole array. You can partition it into [2] , [3,10,7] , and [5,14] . The first subrange has product and LCM equal to 2 . The second has product and LCM equal to 210 . And the third has product and LCM equal to 70 . Another possible partitioning is [2,3] , [10,7] , and [5,14] . The second query asks about the range (2,4) . Its product is equal to its LCM, so you don't need to partition it further. The last query asks about the range (3,5) . You can partition it into [10,7] and [5] . "...