B'We call an array b_1, b_2, ldots, b_m good, if there exist two indices i < 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: 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}) . The first line contains two integers n and q ( 2 <= n <= 194 ,598 , 1 <= q <= 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 <= a_i <= 5 ,032 ,107 ) -- the elements of the array. Each of the next q lines contains two integers l_i and r_i ( 1 <= l_i < r_i <= n ) -- the parameters of a query. Output q lines -- the answers for each query in the order they are given in the input. 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 . '...