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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Vadim Semenov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskH solver = new TaskH();
        solver.solve(1, in, out);
        out.close();
    }

    static final class TaskH {
        private static final int MAX_VALUE = 5032107;
        private static final int[] PRIME_DIVISOR = new int[MAX_VALUE + 1];
        private static final int[] PRIMES_QTY = new int[MAX_VALUE + 1];
        private static final int MAX_QTY;

        static {
            for (int d = 0; d <= MAX_VALUE; ++d) {
                PRIME_DIVISOR[d] = d;
            }
            for (int prime = 2; prime <= MAX_VALUE / prime; ++prime) {
                if (PRIME_DIVISOR[prime] == prime) {
                    for (int number = prime * prime; number <= MAX_VALUE; number += prime) {
                        if (PRIME_DIVISOR[number] == number) {
                            PRIME_DIVISOR[number] = prime;
                        }
                    }
                }
            }
            Arrays.fill(PRIMES_QTY, 1);
            PRIMES_QTY[0] = 0;
            PRIMES_QTY[1] = 0;
            int max = 1;
            for (int number = 4; number <= MAX_VALUE; ++number) {
                int prime = PRIME_DIVISOR[number];
                int divisor = number / prime;
                PRIMES_QTY[number] = PRIME_DIVISOR[divisor] == prime ?
                        PRIMES_QTY[divisor / prime] : (PRIMES_QTY[divisor] + 1);
                max = Math.max(max, PRIMES_QTY[number]);
            }
            MAX_QTY = max;
        }

        public void solve(int __, InputReader in, PrintWriter out) {
            int length = in.nextInt();
            int queries = in.nextInt();
            // aux[divisor][divisorsCount] = max i: a[i] % divisor == 0 && DIVISORS_QTY[a[i] / divisor] == divisorsCount
            int[][] aux = new int[MAX_VALUE + 1][MAX_QTY + 1];
            // maxLeft[answer][right] = max l: answer(left, right) == answer
            int[][] maxLeft = new int[length + 1][2 * MAX_QTY + 1];
            for (int i = 1; i <= length; ++i) {
                System.arraycopy(maxLeft[i - 1], 0, maxLeft[i], 0, maxLeft[i].length);
                int number = in.nextInt();
                int[] factorization = factorize(number);
                for (int mask = (1 << PRIMES_QTY[number]); mask-- > 0; ) {
                    int divisor = getDivisor(factorization, mask);
                    int count = PRIMES_QTY[number] - PRIMES_QTY[divisor];
                    for (int k = 0; k <= MAX_QTY; ++k) {
                        maxLeft[i][k + count] = Math.max(maxLeft[i][k + count], aux[divisor][k]);
                    }
                }
                for (int mask = (1 << PRIMES_QTY[number]); mask-- > 0; ) {
                    int divisor = getDivisor(factorization, mask);
                    int count = PRIMES_QTY[number] - PRIMES_QTY[divisor];
                    aux[divisor][count] = i;
                }
            }
            while (queries-- > 0) {
                int left = in.nextInt();
                int right = in.nextInt();
                int answer = 0;
                while (maxLeft[right][answer] < left) {
                    ++answer;
                }
                out.println(answer);
            }
        }

        private int getDivisor(int[] factorization, int mask) {
            int divisor = 1;
            for (int bit = 32 - Integer.numberOfLeadingZeros(mask); bit >= 0; --bit) {
                if (((mask >>> bit) & 1) == 1) {
                    divisor *= factorization[bit];
                }
            }
            return divisor;
        }

        private int[] factorize(int number) {
            int[] factorization = new int[PRIMES_QTY[number]];
            int ptr = 0;
            while (number > 1) {
                int prime = PRIME_DIVISOR[number];
                int power = 0;
                while (number % prime == 0) {
                    number /= prime;
                    power++;
                }
                if (power % 2 != 0) {
                    factorization[ptr++] = prime;
                }
            }
            assert ptr == factorization.length;
            return factorization;
        }

    }

    static class InputReader {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(readLine());
            }
            return tokenizer.nextToken();
        }

        public String readLine() {
            String line;
            try {
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }

    }
}