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

public class H {
	static PrintWriter out = new PrintWriter(System.out);

	static int N, Q, MAX = 5_032_107 + 1;
	static int[] ar;
	static int[] bits;
	static int[][] factors;
	static int[] primes;
	static Query qs[];
	
	static final boolean debug = false;
	
	public static void main(String[] args) {
		FS in = new FS();
		
		boolean isPrime[] = new boolean[MAX];
		primes = new int[MAX];
		int pId = 0;
		Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false;
		for(int i = 2; i < MAX; i++) {
			if(isPrime[i]) {
				primes[pId++] = i;
				for(int j = 2*i; j < MAX; j += i) isPrime[j] = false;
			}
		}
		
		
		N = in.nextInt();
		Q = in.nextInt();
		ar = new int[N];
		for(int i = 0; i < N; i++) ar[i] = in.nextInt();
		qs = new Query[Q];
		for(int i = 0; i < Q; i++) qs[i] = new Query(in.nextInt()-1, in.nextInt()-1, i);
		
		factors = new int[N][];
		bits = new int[N];
		for(int i = 0; i < N; i++) {
			compress(i);
		}
		
		if(debug) {
			for(int i = 0; i < N; i++) {
				System.out.print(ar[i]+" bits="+bits[i]+"  fs=");
				System.out.println(Arrays.toString(factors[i]));
			}
		}
		
		ArrayList<Query> qsAt[] = new ArrayList[N];
		for(int i = 0; i < N; i++) qsAt[i] = new ArrayList<Query>();
		for(Query q : qs) qsAt[q.r].add(q);
		int answers[] = new int[Q];
		Arrays.fill(answers,-1);
		
		int MAX_ANS = 16;
		int MAX_TO = MAX_ANS/2;
		int latestMake[][] = new int[MAX_TO][MAX];
		for(int a[] : latestMake) Arrays.fill(a, -1);
		
		int latestForAnswer[] = new int[MAX_ANS];
		Arrays.fill(latestForAnswer, -1);
		
		for(int i = 0; i < N; i++) {
			if(debug) System.out.println("Processing: "+ar[i]);
			//combine with previous answers
			for(int j = 0; j < factors[i].length; j++) {
				if(debug) System.out.println("  factor: "+factors[i][j]);
				int toMake = bits[i] - Integer.bitCount(j);
				int val = factors[i][j];
				for(int from = 0; from < MAX_TO; from++) {
					if(latestMake[from][val] != -1) {
						latestForAnswer[from+toMake] = Math.max(latestForAnswer[from+toMake], latestMake[from][val]);
						if(debug) System.out.println("   from="+from+"   latest of "+(from+toMake)+" now "+latestMake[from][val]);
					}
				}
			}
			
			//update current answers
			for(int j = 0; j < factors[i].length; j++) {
				int toMake = bits[i] - Integer.bitCount(j);
				int val = factors[i][j];
				latestMake[toMake][val] = i;
				if(debug) System.out.println("   Can make "+val+" with "+toMake);
			}
			
			for(Query q : qsAt[i]) {
				for(int j = 0; j < MAX_ANS; j++) {
					if(latestForAnswer[j] >= q.l) { answers[q.id] = j; break;}
				}
				if(debug) System.out.println("PROCESSING QUERY "+q.l+" "+q.r+" res="+answers[q.id]);

			}
		}
		
		for(int ii : answers) out.println(ii);
		out.close();
	}
	
	static void compress(int id) {
		ArrayList<Integer> pfs = new ArrayList<Integer>();
		int res = 1;
		int val = ar[id];
		for(int i = 0;;i++) {
			if(primes[i]*primes[i] > val || val == 1) break;
			int parity = 0;
			while(val%primes[i] == 0) {
				val /= primes[i];
				parity ^= 1;
			}
			if(parity == 1) { pfs.add(primes[i]); res *= primes[i]; }
 		}
		if(val != 1) { pfs.add(val); res *= val;}

		ar[id] = res;
		bits[id] = pfs.size();
		factors[id] = new int[1<<pfs.size()];
		for(int m = 0; m < 1<<pfs.size(); m++) {
			int add = 1;
			for(int i = 0; i < pfs.size(); i++) if((m & (1<<i)) > 0) add *= pfs.get(i);
			factors[id][m] = add;
		}
	}
		
	
	static class Query{
		int l,r,id;
		public Query(int ll, int rr, int ii) {
			l=ll;
			r=rr;
			id=ii;
		}
	}
	
	static class FS{
		BufferedReader br;
		StringTokenizer st;
		public FS() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {st = new StringTokenizer(br.readLine());}
				catch(Exception e) { throw null;}
			}
			return st.nextToken();
		}
		int nextInt() { return Integer.parseInt(next());}
		double nextDouble() { return Double.parseDouble(next());}
		long nextLong() { return Long.parseLong(next());}
		int[] NIA(int n) {
			int r[] = new int[n];
			for(int i = 0; i < n; i++) r[i] = nextInt();
			return r;
		}
		long[] NLA(int n) {
			long r[] = new long[n];
			for(int i = 0; i < n; i++) r[i] = nextLong();
			return r;
		}
		char[][] grid(int r, int c){
			char res[][] = new char[r][c];
			for(int i = 0; i < r; i++) {
				char l[] = next().toCharArray();
				for(int j = 0; j < c; j++) {
					res[i][j] = l[j];
				}
			}
			return res;
		}
	}
	
}