You have written on a piece of paper an array of n positive integers a[1], a[2], ..., a[n] and m good pairs of integers (i1, j1), (i2, j2), ..., (im, jm). Each good pair (ik, jk) meets the following conditions: ik + jk is an odd number and 1 ≤ ik < jk ≤ n.

In one operation you can perform a sequence of actions: 

  * take one of the good pairs (ik, jk) and some integer v (v > 1), which divides both numbers a[ik] and a[jk]; 
  * divide both numbers by v, i. e. perform the assignments: <image> and <image>. 



Determine the maximum number of operations you can sequentially perform on the given array. Note that one pair may be used several times in the described operations.

Input

The first line contains two space-separated integers n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100).

The second line contains n space-separated integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — the description of the array.

The following m lines contain the description of good pairs. The k-th line contains two space-separated integers ik, jk (1 ≤ ik < jk ≤ n, ik + jk is an odd number).

It is guaranteed that all the good pairs are distinct.

Output

Output the answer for the problem.

Examples

Input

3 2
8 3 8
1 2
2 3


Output

0


Input

3 2
8 12 8
1 2
2 3


Output

2
// Main Code at the Bottom
import java.util.*;
import java.io.*; 
public class Main{
	//Fast IO class
    static class FastReader {
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader() {
        	boolean env=System.getProperty("ONLINE_JUDGE") != null;
        	if(!env) {
        		try {
					br=new BufferedReader(new FileReader("src\\input.txt"));
				} catch (FileNotFoundException e) {
					e.printStackTrace();
				}
        	}
        	else br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) {
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
        int nextInt() {
            return Integer.parseInt(next()); 
        } 
        long nextLong() {
            return Long.parseLong(next()); 
        } 
        double nextDouble() {
            return Double.parseDouble(next()); 
        } 
        String nextLine() {
            String str = ""; 
            try {
                str = br.readLine(); 
            } 
            catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }     
    static long MOD=1000000000+7;
    //debug
    static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
    // Pair
    static class pair{
    	long x,y;
    	pair(long a,long b){
    		this.x=a;
    		this.y=b;
    	}
    	public boolean equals(Object obj) {
    		if(obj == null || obj.getClass()!= this.getClass()) return false;
            pair p = (pair) obj;
            return (this.x==p.x && this.y==p.y);
        }
    	public int hashCode() {
            return Objects.hash(x,y);
        }
    }
    static FastReader sc=new FastReader();
    static PrintWriter out=new PrintWriter(System.out);  
    //Global variables and functions
    //Dinic's algo O(EV^2)
    // For bipartite matching O(sqrt(V)E)
    static class edge{
    	int src,dest,cap,flow;
    	edge(int s,int d,int c){
    		src=s;
    		dest=d;
    		cap=c;
    		flow=0;
    	}
    }
    static class dinic{
    	int inf=(int)1e8;
    	ArrayList<edge> edges;
    	ArrayList<Integer> graph[];
    	int n,m=0,s,t;
    	int level[],next[];
    	Queue<Integer> q;
    	dinic(int n,int s,int t){
    		this.n=n;
    		this.s=s;
    		this.t=t;
    		graph=new ArrayList[n];
    		edges=new ArrayList<>();
    		for(int i=0;i<n;i++) graph[i]=new ArrayList<>();
    		level=new int[n];
    		next=new int[n];
    	}
    	void addEdge(int s,int d,int c) {
    		edges.add(new edge(s,d,c));
    		edges.add(new edge(d,s,0));
    		graph[s].add(m);
    		graph[d].add(m+1);
    		m+=2;
    	}
    	boolean bfs() {
    		Arrays.fill(level, -1);
			level[s]=0;
			q=new LinkedList<>();
			q.add(s);
    		while(!q.isEmpty()) {
    			int v=q.poll();
    			for(Integer id: graph[v]) {
    				if(edges.get(id).cap-edges.get(id).flow<1) continue;
    				if(level[edges.get(id).dest]!=-1) continue;
    				level[edges.get(id).dest]=level[v]+1;
    				q.add(edges.get(id).dest);
    			}
    		}
    		return level[t]!=-1;
    	}
    	int dfs(int s,int pushed) {
    		if(pushed==0) return 0;
    		if(s==t) return pushed;
    		for(;next[s]<graph[s].size();next[s]++) {
    			int id=graph[s].get(next[s]);
    			int x=edges.get(id).dest;
    			if(level[s]+1!=level[x] || edges.get(id).cap-edges.get(id).flow<1) continue;
    			int val=dfs(x,Math.min(pushed, edges.get(id).cap-edges.get(id).flow));
    			if(val==0) continue;
    			edges.get(id).flow+=val;
    			edges.get(id^1).flow-=val;
    			return val;
    		}
    		return 0;
    		
    	}
    	int maxFlow() {
    		int flow=0;
    		while(bfs()) {
    			Arrays.fill(next, 0);
    			while(true) {
    				int bottleneck=dfs(s,inf);
    				if(bottleneck==0) break;
    				flow+=bottleneck;
    			}
    		}
    		return flow;
    	}
    }
    //Main function(The main code starts from here)
    public static void main (String[] args) throws java.lang.Exception {
    	int test=1;
    	//test=sc.nextInt();
    	while(test-->0){
    		int n=sc.nextInt(),m=sc.nextInt(),cnt=0;
    		ArrayList<int[]> a[]=new ArrayList[n];
    		for(int i=0;i<n;i++) {
    			int x=sc.nextInt();
    			ArrayList<int[]> tmp=new ArrayList<>();
    			for(int j=2;j*j<=x;j++) {
    				while(x%j==0) {
    					tmp.add(new int[] {j,cnt++});
    					x/=j;
    				}
    			}
    			if(x>1) tmp.add(new int[] {x,cnt++});
    			a[i]=tmp;
    		}
    		int s=cnt++,t=cnt++;
    		dinic solver=new dinic(cnt,s,t);
    		while(m-->0) {
    			int i=sc.nextInt()-1,j=sc.nextInt()-1;
    			if(i%2==1) {
    				int tmp=i;
    				i=j;
    				j=tmp;
    			}
    			for(int x[]: a[i]) {
    				for(int y[]: a[j]) {
    					if(x[0]==y[0]) solver.addEdge(x[1],y[1],1);
    				}
    			}
    		}
    		for(int i=0;i<n;i++) {
    			if(i%2==0) {
    				for(int x[]: a[i]) solver.addEdge(s,x[1],1);
    			}
    			else {
    				for(int x[]: a[i]) solver.addEdge(x[1],t,1);
    			}
    		}
    		out.println(solver.maxFlow());
    	}	
        out.flush();
        out.close();
    }
}