Consider a sequence of distinct integers a_1, …, a_n, each representing one node of a graph. There is an edge between two nodes if the two values are not coprime, i. e. they have a common divisor greater than 1.

There are q queries, in each query, you want to get from one given node a_s to another a_t. In order to achieve that, you can choose an existing value a_i and create new value a_{n+1} = a_i ⋅ (1 + a_i), with edges to all values that are not coprime with a_{n+1}. Also, n gets increased by 1. You can repeat that operation multiple times, possibly making the sequence much longer and getting huge or repeated values. What's the minimum possible number of newly created nodes so that a_t is reachable from a_s?

Queries are independent. In each query, you start with the initial sequence a given in the input.

Input

The first line contains two integers n and q (2 ≤ n ≤ 150 000, 1 ≤ q ≤ 300 000) — the size of the sequence and the number of queries.

The second line contains n distinct integers a_1, a_2, …, a_n (2 ≤ a_i ≤ 10^6, a_i ≠ a_j if i ≠ j).

The j-th of the following q lines contains two distinct integers s_j and t_j (1 ≤ s_j, t_j ≤ n, s_j ≠ t_j) — indices of nodes for j-th query.

Output

Print q lines. The j-th line should contain one integer: the minimum number of new nodes you create in order to move from a_{s_j} to a_{t_j}.

Examples

Input


3 3
2 10 3
1 2
1 3
2 3


Output


0
1
1


Input


5 12
3 8 7 6 25
1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5


Output


0
1
0
1
0
1
0
1
1
1
1
2

Note

In the first example, you can first create new value 2 ⋅ 3 = 6 or 10 ⋅ 11 = 110 or 3 ⋅ 4 = 12. None of that is needed in the first query because you can already get from a_1 = 2 to a_2 = 10.

In the second query, it's optimal to first create 6 or 12. For example, creating 6 makes it possible to get from a_1 = 2 to a_3 = 3 with a path (2, 6, 3).

<image>

In the last query of the second example, we want to get from a_3 = 7 to a_5 = 25. One way to achieve that is to first create 6 ⋅ 7 = 42 and then create 25 ⋅ 26 = 650. The final graph has seven nodes and it contains a path from a_3 = 7 to a_5 = 25.
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
public  class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 1000000007;
    long fac[]= new long[1000001];
    long inv[]=new long[1000001];
    public  void solve() throws IOException 
    {

        
         
        int n = readInt();
        int q= readInt();

        int arr[]=new int[n+1];
        for(int i=1;i<=n;i++)
            arr[i]= readInt();

        int prime[]=new int[1000010];

        for(int i=1;i<=1000001;i++)
        {
             prime[i]=-1;
        }

        for(int i=2;i<=1000001;i++)
        {
           if(prime[i]==-1)
           {
            for(int j=i;j<=1000001;j=j+i)
            {
                if(prime[j]==-1)
                {
                    prime[j]=i;
                } 
            }
           }
        }

        int parent[]=new int[1000000+2];
        for(int i=1;i<=1000001;i++)
        {
            parent[i]=i;
        }
        
        for(int i=1;i<=n;i++)
        {
            int last =0;
            int val = arr[i];
            while(val!=1)
            {
                int pal = prime[val];
                if((pal!=last)&&(last!=0))
                {
                   union(parent,pal,last);
                }
                last=pal;
                val = val/pal;
            }
        }
        
        HashMap<Long,Integer> map=new HashMap<Long,Integer>();
        for(int i=1;i<=n;i++)
        {
          if(arr[i]==1)
          {

            long par1 = find(parent,1);
            long par2 = find(parent,2);
            if(par1>par2)
            {
                long temp = par1;
                par1=par2;
                par2= temp;
            }
            long c = par1+(1000010)*par2;
            map.put(c,1);
          }
          else
          {
             int stack[]=new int[20];
             int top=-1;
             top++;
             stack[top]= find(parent,prime[arr[i]]);
  

             int val = arr[i]+1;
             while(val!=1)
             {
                 int c = prime[val];
                 top++;
                 stack[top]=c;
                 val= val/c;
             }

             for(int c =0;c<=top;c++)
             {
                 for(int j =c+1;j<=top;j++)
                 {
                    long par1 = find(parent,stack[c]);
                    long par2 = find(parent,stack[j]);
                    if(par1!=par2)
                    {
                        if(par1>par2)
                        {
                            long temp = par1;
                            par1=par2;
                            par2= temp;
                        }
                        long gal = par1+ 1000010*par2;
                        map.put(gal,1);
                    }
                 }
             }

          }
        }

        for(int i=1;i<=q;i++)
        {

             long s = readInt();
             long tl = readInt();
             s= arr[(int)s];
             tl = arr[(int)tl];

             if(s!=1)
             {
                 s=prime[(int)s];
             }
             if(tl!=1)
             {
                 tl =prime[(int)tl];
             }

             s= find(parent,(int)s);
             tl = find(parent,(int)tl);
             if(s==tl)
                out.println(0);
             else
             {
             if(s>tl)
             {
                long temp = s;
                s= tl;
                tl= temp;
             }
              s= s+ tl*1000010;
              if(map.containsKey(s))
                out.println(1);
              else
                out.println(2);
            }


        }





        



    }
    public void union(int parent[] , int u , int v )
    {
               int par1= find(parent,u);
               int par2 = find(parent,v);
               if(par1!=par2)
               {
                 parent[par1]=par2;

               }
    }
    public int find(int parent[] , int i)
    {
              if(parent[i]==i)
              {
                return i;
              }
              parent[i]= find(parent,parent[i]);
              return parent[i];
    }
    
    public int value (int seg[], int left , int right ,int index, int l, int r)
    {
            
            if(left>right)
            {
              return -100000000;
            }
            if(right<l||left>r)
                return -100000000;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val = value(seg,left,mid,2*index+1,l,r);
            int val2 = value(seg,mid+1,right,2*index+2,l,r);
            return Math.max(val,val2);

    }
   
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    long u ;
    long v;
    
    edge(long u, long v)
    {
       this.u=u;
       this.v=v;
    }
    public int compareTo(edge e)
    {
        if(this.v>=e.v)
        return 1;
        else
        return -1;

    }
}