Problem: We call an array b_1, b_2, …, b_m good, if there exist two indices i < j such that b_i ⋅ b_j is a [perfect square](https://en.wikipedia.org/wiki/Square_number).

Given an array b_1, b_2, …, 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, …, 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, …, a_n and q queries of the form l_i, r_i. For each query output f(a_{l_i}, a_{l_i + 1}, …, a_{r_i}).

Input

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, …, 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

Output q lines — the answers for each query in the order they are given in the input.

Example

Input

10 10
34 37 28 16 44 36 43 50 22 13
1 3
4 8
6 10
9 10
3 10
8 9
5 6
1 4
1 7
2 6


Output

2
0
1
3
0
1
1
1
0
0

Note

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 ⋅ a_3 = 268 324 = 518^2.

In the second query subarray is already good because a_4 ⋅ a_6 = 24^2.

In the third query you can divide 50 by 2 to get 25. Then a_6 ⋅ a_8 = 30^2.

Solution (in JAVA):

Solution:

import java.util.ArrayList;
import java.util.Scanner;
import java.io.*;

public class Main {

    public static void calc_dlin(int[] prost, ArrayList<Integer> aList[][], int glub, int sum, int mnog, int i, int[][] min_dlin_right, int[][] kek, int lol[]) {
        if (glub > prost[0]) {
            if (mnog != 1) {
                for (int x = 0; x < kek.length; x ++) {
//                    if (aList[x][mnog] != null) {
//                        int mas_begin = 1, mas_end = aList[x][mnog].size() - 1;
////                        int znach = 0;
////                        while (mas_begin <= mas_end) {
////                            znach = aList[x][mnog].get((mas_begin + mas_end) / 2);
////                            if (znach > i && ((mas_begin + mas_end) / 2 == 1 || aList[x][mnog].get((mas_begin + mas_end) / 2 - 1) <= i)){
////                                break;
////                            }
////                            if (znach > i) {
////                                mas_end = (mas_begin + mas_end) / 2 - 1;
////                            } else {
////                                mas_begin = (mas_begin + mas_end) / 2 + 1;
////                            }
////                        }
//                        int min_pos = (mas_begin + mas_end) / 2 ;
//                        int prom_a = prost[0] - 2 * aList[x][mnog].get(0) + x, prom_b = aList[x][mnog].get(min_pos);
//                        if (min_dlin_right[prom_b][prom_a] < i && prom_b > i) {
//                            min_dlin_right[prom_b][prom_a] = i;
//                        }
//                    }
                    if (kek[x][mnog] != -1) {
                        int prom_a = prost[0] - 2 * (sum - 1) + x;//, prom_b = aList[x][mnog].get(min_pos);
                        if (min_dlin_right[i][prom_a] < kek[x][mnog]) {
                            min_dlin_right[i][prom_a] = kek[x][mnog];
                        }
                    }
                }
                kek[prost[0]][mnog] = i;
            }
        } else {
            calc_dlin(prost, aList, glub + 1, sum, mnog, i, min_dlin_right, kek, lol);
            calc_dlin(prost, aList, glub + 1, sum + 1, mnog * prost[glub], i, min_dlin_right, kek, lol);
        }
    }

    public static void calc(int[] prost, ArrayList<Integer> aList[][], int glub, int sum, int mnog, int i) {
        if (glub > prost[0]) {
            if (mnog != 1) {
                if (aList[prost[0]][mnog] == null) {
                    aList[prost[0]][mnog] = new ArrayList<Integer>();
                    aList[prost[0]][mnog].add(sum - 1);
                }
                aList[prost[0]][mnog].add(i);
            }
        } else {
            calc(prost, aList, glub + 1, sum, mnog, i);
            calc(prost, aList, glub + 1, sum + 1, mnog * prost[glub], i);
        }
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int resheto[] = new int[(int)(Math.ceil(Math.sqrt(5032108) + 10))], prost[] = new int[400000], kl = 0, max_mnog = -1;
//        int a_array[] = new int[200];
//        int m=100000;
//        for (int i = 0; i < a_array.length; i ++)
//            a_array[i] = (int)(Math.random() * (500000)) ;;
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int a_array[] = new int[n];
        for (int i = 0; i < a_array.length; i ++)
            a_array[i] = in.nextInt();
        int tests_array[][] = new int[m][2];
        for (int i = 0; i < tests_array.length; i ++) {
            tests_array[i][0] = in.nextInt() - 1;
            tests_array[i][1] = in.nextInt() - 1;
//            tests_array[i][0] = (int)(Math.random() * (a_array.length - 1)) ;
//            tests_array[i][1] = (int)(Math.random() * (a_array.length - tests_array[i][0] - 1) + tests_array[i][0] + 1);
        }
        int a_prost[][] = new int[a_array.length][8];
        int a_len[][] = new int [8][a_array.length + 2];
        for (int i = 2; i * i < resheto.length; i++) {
            if (resheto[i] == 0) {
                for (int j = i * i; j < resheto.length; j += i) {
                    resheto[j] = 1;
                }
            }
        }
        for (int i = 2; i < resheto.length; i++) {
            if (resheto[i] == 0) {
                prost[kl] = i;
                kl++;
            }
        }
        for (int i = 0; i < a_array.length; i++) {
            int cop = a_array[i];
            for (int j = 0; j < prost.length && prost[j] * prost[j] <= a_array[i]; j++) {
                int krat = 0;

                while (cop % prost[j] == 0) {
                    krat++;
                    cop = cop / prost[j];
                }
                if (krat % 2 == 1) {
                    a_prost[i][0]++;
                    a_prost[i][a_prost[i][0]] = prost[j];
                }
            }
            if (cop != 1) {
                a_prost[i][0]++;
                a_prost[i][a_prost[i][0]] = cop;
            }
            if (max_mnog < a_prost[i][0])
                max_mnog = a_prost[i][0];
            a_len[a_prost[i][0]][0]++;
            a_len[a_prost[i][0]][a_len[a_prost[i][0]][0]] = i;
        }
        ArrayList<Integer> aList[][] = new ArrayList[max_mnog + 1][5032108];
        int min_dlin_right[][] = new int[a_array.length][2 * (8)];

        for (int i = 0; i < min_dlin_right.length; i ++)
            for (int j = 0; j < min_dlin_right[i].length; j ++) {
                min_dlin_right[i][j] = -1;
            }


//        for (int i = 0; i < a_prost.length; i++){
//            calc(a_prost[i], aList, 1,1,1, i);
//        }
        int kek[][] = new int[16][6000000];
        int lol[] = new int[10];
        for (int i = 0; i < lol.length; i++)
            lol[i] = -1;
        for (int i = 0; i < kek.length; i++)
            for (int j = 0; j < kek[i].length; j++){
                kek[i][j] = -1;
            }

        for (int i = 0; i < min_dlin_right.length; i++){
            calc_dlin(a_prost[i], aList, 1,1,1, i,min_dlin_right, kek, lol);
            for (int keka = 0; keka < lol.length; keka++) {
                //  System.out.printf("%d %d %d %d\n",i,keka,min_dlin_right[i][keka + prost[0]] , lol[keka]);
                if (keka + a_prost[i][0]<16 && min_dlin_right[i][keka + a_prost[i][0]] < lol[keka])
                    min_dlin_right[i][keka + a_prost[i][0]] = lol[keka];
            }
            lol[a_prost[i][0]] = i;
        }
//
//        for (int i = 0; i < min_dlin_right.length; i++) {
//            for (int x = 0; x < a_len.length; x++) {
//                int mas_begin = 1, mas_end = a_len[x][0];
//                while (mas_begin <= mas_end) {
//                    int znach = a_len[x][(mas_begin + mas_end) / 2];
//                    if (znach < i && ((mas_begin + mas_end) / 2 == a_len[x][0] || a_len[x][(mas_begin + mas_end) / 2 + 1] >= i)) {
//                        break;
//                    }
//                    if (znach < i) {
//                        mas_begin = (mas_begin + mas_end) / 2 + 1;
//                    } else {
//                        mas_end = (mas_begin + mas_end) / 2 - 1;
//                    }
//                }
//                if ((min_dlin_right[i][a_prost[i][0] + x] < a_len[x][(mas_begin + mas_end) / 2]) &&
//                        i > a_len[x][(mas_begin + mas_end) / 2] && a_len[x][0] > 0 && (mas_begin + mas_end) / 2 > 0)
//                    min_dlin_right[i][a_prost[i][0] + x] = a_len[x][(mas_begin + mas_end) / 2];
//            }
//        }

        for (int i = 1; i < min_dlin_right.length; i++) {
            for (int j = 0; j < min_dlin_right[i].length; j++) {
                if (min_dlin_right[i][j] < min_dlin_right[i - 1][j] && min_dlin_right[i - 1][j] >= 0)
                    min_dlin_right[i][j] = min_dlin_right[i - 1][j];
            }
        }
//        for (int i = 0; i < min_dlin_right.length; i++){
//            System.out.printf("%d %d", a_array[i], i);
//            for (int j = 0; j < min_dlin_right[i].length; j++) {
//                System.out.printf("  %d - %d  ", j, min_dlin_right[i][j]);
//            }
//            System.out.println();
//        }
//        for ( int i = 0; i < lol.length; i ++)
//            System.out.println(lol[i]);
        PrintWriter my_outer = new PrintWriter(System.out);
        for (int i  = 0; i < m; i++) {

            for (int j = 0; j < 16; j++) {
                if (min_dlin_right[tests_array[i][1]][j] >= tests_array[i][0]){
                    my_outer.println(j);
                    break;
                }

            }
        }
        my_outer.flush();
        my_outer.close();
        //System.out.println(s + qwe);
//        System.out.println(otrezok_dlin + "  " + otrezok_count);

//        System.out.println(max_mnog);
//        for (int x = 0; x < aList.length; x++) {
//            for (int i = 0; i < aList[x].length; i++) {
//                if (aList[x][i] != null) {
//                    System.out.printf("%d %d ", x, i);
//                    for (int j = 0; j < aList[x][i].size(); j++) {
//                        System.out.printf("%d ", aList[x][i].get(j));
//                    }
//                    System.out.println();
//                }
//            }
//        }
//        System.out.println();
//        System.out.println();
//        for (int i = 0; i < a_prost.length; i++){
//            System.out.printf("%d %d: ",i,a_array[i]);
//            for (int j = 0; j <= a_prost[i][0]; j++) {
//                System.out.printf("%d ",a_prost[i][j]);
//            }
//            System.out.println();
//        }
//        System.out.println();
//        System.out.println();
//        for (int i = 0; i < a_len.length; i++){
//            System.out.printf("%d ", i);
//            for (int j = 1; j <= a_len[i][0]; j++) {
//                System.out.printf("  %d - %d - %d ", j, a_len[i][j], a_array[a_len[i][j]]);
//            }
//            System.out.println();
//        }
//        System.out.println();
//        System.out.println();
//        for (int i = 0; i < min_dlin.length; i++){
//            System.out.printf("%d %d", a_array[i], i);
//            for (int j = 0; j < min_dlin[i].length; j++) {
//                System.out.printf("  %d - %d  ", j, min_dlin[i][j]);
//            }
//            System.out.println();
//        }
//        System.out.println();
//        System.out.println();

//        System.out.println();
//        System.out.println();
//        for (int i = 0; i < dlin_otrezok.length; i++){
//            for (int j = i; j < dlin_otrezok[i].length; j++) {
//                System.out.printf("%d %d %d   %d - %d\n", i, j, dlin_otrezok[i][j], i * otrezok_dlin, (j+1) * otrezok_dlin - 1);
//            }
//        }
        // Scanner in = new Scanner(System.in);
//        System.out.println(1321321321);
//        for (int i = 0; i < tests_array.length; i++){
//            int test_min = 9999999,x1 = 0,y1 = 0;
//            //System.out.printf("%d %d",tests_array[i][0],tests_array[i][1]);
//            for (int j = tests_array[i][0]; j <= tests_array[i][1] - 1; j ++) {
//
//                for (int x = j + 1; x <= tests_array[i][1]; x ++) {
//                    int a1 = 1, a2 = 1, test_count = 0;
//                    while (a1 <= a_prost[j][0] && a2 <= a_prost[x][0]) {
//                        if (a_prost[j][a1] < a_prost[x][a2]) {
//                            test_count++;
//                            a1++;
//                            continue;
//                        }
//                        if (a_prost[j][a1] > a_prost[x][a2]) {
//                            test_count++;
//                            a2++;
//                            continue;
//                        }
//                        if (a_prost[j][a1] == a_prost[x][a2]) {
//                            a2++;
//                            a1++;
//                            continue;
//                        }
//                    }
//                   // System.out.printf("%d %d %d\n",a1,a2,test_count);
//                    if (a1 <= a_prost[j][0])
//                        test_count += a_prost[j][0] - a1 + 1;
//                    if (a2 <= a_prost[x][0])
//                        test_count += a_prost[x][0] - a2 + 1;
//                    if (test_count < test_min) {
//                        test_min = test_count;
//                        x1=j;y1=x;
//                    }
//                }
//            }
//            int klonono = 999999;
//            for (int jo = 0; jo < 16; jo++) {
//                if (min_dlin_right[tests_array[i][1]][jo] >= tests_array[i][0]){
//                    klonono = jo;
//                    break;
//                }
//
//            }
//            if (test_min != klonono) {
//                System.out.printf("%d %d %d %d %d %d\n",tests_array[i][0],tests_array[i][1],test_min,klonono,x1,y1);
//            }
//        }
        //in.close();
//        System.out.println();
//        System.out.println();
//        for (int i = 0; i < dlin_otrezok.length; i++){
//            System.out.printf("%d %d   %d - %d\n", i, dlin_otrezok[i], i * otrezok_dlin, (i + 1) * otrezok_dlin - 1);
//        }
    }
}