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.*;
import java.io.*;

public class A {

	
	static int maxN=5032108,maxDiv=7;
	static 	int []numDiv;
	static int [][]primeDiv;
	static int []getDiv(int x)
	{
		int n=1<<(numDiv[x]);
		
		int []ans=new int [n+1];
		
		for(int msk=0;msk<n;msk++)
		{
			int div=1;
			for(int j=0;j<numDiv[x];j++)
				if((msk & (1<<j)) !=0)
					div*=primeDiv[j][x];
			ans[msk]=div;
		}
		ans[ans.length-1]=1;
		return ans;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n=sc.nextInt(),q=sc.nextInt();
		int []a=new int [n];
		
		boolean []isPrime = new boolean[maxN];
		int []distinct=new int [maxN];
		for(int i=0;i<maxN;i++)
			distinct[i]=i;
		
		Arrays.fill(isPrime, true);
	
		primeDiv= new int [maxDiv][maxN];
		numDiv=new int [maxN];
	
		for(int i=2;i<maxN;i++)
			if(isPrime[i])
			{
				
				primeDiv[numDiv[i]++][i]=i;
				for(int j=i+i;j<maxN;j+=i)
				{
					int x=distinct[j];
					long sq=i*1L*i;
					while(x%sq==0)
						x/=sq;
					distinct[j]=x;
					if(x%i==0)
					{
						primeDiv[numDiv[j]++][j]=i;
						
					}
					isPrime[j]=false;
				}
			}
	
	
		
		for(int i=0;i<n;i++)
		{
			int x=sc.nextInt();
			int y=1;
			for(int j=0;j<numDiv[x];j++)
				y=y*primeDiv[j][x];
			a[i]=y;
			
		}
		
		// dp  [dis][val] = the rightmost i such that a[i] = val * x where x can be represented as the product of 
		// dis distinct primes
		int [][]dp=new int [maxDiv+1][maxN];
		for(int []x:dp)
			Arrays.fill(x, -1);
		// best [D] = the righmost l such that the ans for [l,i] = D
		int []print=new int [q];
		int []best=new int [15];
		Arrays.fill(best, -5);
		query[] queries = new query[q];
		for(int i=0;i<q;i++)
			queries[i]=new query(sc.nextInt()-1,sc.nextInt()-1,i);
		Arrays.sort(queries, (x,y)->x.r-y.r);
		int i=0;
		for(query query:queries)
		{
			int l=query.l,r=query.r;
			
			while(i<=r)
			{
				int x=a[i];
				int []divisors=getDiv(x);
				for(int val:divisors)
				{
					int dis=numDiv[x/val];
					for(int k=0;k<=maxDiv;k++)
						best[k+dis]=Math.max(best[k+dis], dp[k][val]);
				}
				for(int val:divisors)
				{
					int dis=numDiv[x/val];
					dp[dis][val]=i;
				}
				i++;
			}
			
			int ans=-1;
			for(int j=0;j<best.length;j++)
				if(best[j]>=l)
				{
					ans=j;
					break;
				}
			print[query.idx]=ans;
		}
		for(int x:print)
			out.println(x);
		out.close();
	}
	static class query{
		int l,r,idx;
		query(int a,int b,int i){
			l=a;
			r=b;
			idx=i;
		}
		
	}
	
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}
		public Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		public Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}
	}

}