H. Make Squaretime limit per test7 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputWe 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:   multiply any element b_i by any prime p;  divide any element b_i by prime p, if b_i is divisible by p. 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}).InputThe first line contains two integers n and q (2 \le n \le 194\,598, 1 \le q \le 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 \le a_i \le 5\,032\,107) — the elements of the array.Each of the next q lines contains two integers l_i and r_i (1 \le l_i < r_i \le n) — the parameters of a query.OutputOutput q lines — the answers for each query in the order they are given in the input.ExampleInput10 1034 37 28 16 44 36 43 50 22 131 34 86 109 103 108 95 61 41 72 6Output2013011100NoteIn 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.
Input10 1034 37 28 16 44 36 43 50 22 131 34 86 109 103 108 95 61 41 72 6
Output2013011100
['math', '*2900']