CF1516D Cut

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: - he picks a range $ (l, r) $ and cuts the subsegment $ a_l, a_{l + 1}, \ldots, a_r $ out, removing the rest of the array. - he then cuts this range into multiple subranges. - to add a number theory spice to it, he requires that the elements of every subrange must have their product equal to their [least common multiple (LCM)](https://en.wikipedia.org/wiki/Least_common_multiple). 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.

N/A

N/A

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] $ .