#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
const int maxm = 1000000;
const int oo = 0x3f3f3f3f;
struct Edge {
  int u, v, w;
  int next;
};
struct SAP {
  int idx;
  int cur[maxn], pre[maxn];
  int dis[maxn], gap[maxn];
  int aug[maxn], head[maxn];
  Edge edge[maxm];
  void init() {
    idx = 0;
    memset(head, -1, sizeof(head));
  }
  void addedge(int u, int v, int w) {
    edge[idx].u = u;
    edge[idx].v = v;
    edge[idx].w = w;
    edge[idx].next = head[u];
    head[u] = idx++;
    edge[idx].u = v;
    edge[idx].v = u;
    edge[idx].w = 0;
    edge[idx].next = head[v];
    head[v] = idx++;
  }
  int solve(int s, int e, int n) {
    int max_flow = 0, v, u = s;
    int id, mindis;
    aug[s] = oo;
    pre[s] = -1;
    memset(dis, 0, sizeof(dis));
    memset(gap, 0, sizeof(gap));
    gap[0] = n;
    for (int i = 0; i <= n; ++i) {
      cur[i] = head[i];
    }
    while (dis[s] < n) {
      bool flag = false;
      if (u == e) {
        max_flow += aug[e];
        for (v = pre[e]; v != -1; v = pre[v]) {
          id = cur[v];
          edge[id].w -= aug[e];
          edge[id ^ 1].w += aug[e];
          aug[v] -= aug[e];
          if (edge[id].w == 0) u = v;
        }
      }
      for (id = cur[u]; id != -1; id = edge[id].next) {
        v = edge[id].v;
        if (edge[id].w > 0 && dis[u] == dis[v] + 1) {
          flag = true;
          pre[v] = u;
          cur[u] = id;
          aug[v] = min(aug[u], edge[id].w);
          u = v;
          break;
        }
      }
      if (flag == false) {
        if (--gap[dis[u]] == 0) break;
        mindis = n;
        cur[u] = head[u];
        for (id = head[u]; id != -1; id = edge[id].next) {
          v = edge[id].v;
          if (edge[id].w > 0 && dis[v] < mindis) {
            mindis = dis[v];
            cur[u] = id;
          }
        }
        dis[u] = mindis + 1;
        gap[dis[u]]++;
        if (u != s) u = pre[u];
      }
    }
    return max_flow;
  }
};
SAP solver;
bool isp[100005];
vector<long long> p;
void init() {
  memset(isp, true, sizeof(isp));
  for (long long i = 2; i < 100005; ++i) {
    if (isp[i]) {
      p.push_back(i);
      for (long long j = i * i; j < 100005; j += i) {
        isp[j] = false;
      }
    }
  }
}
int a[105];
int n, m, idx;
map<int, int> mp[105];
void divide(int pos, long long num) {
  for (int i = 0; i < p.size(); ++i) {
    if (p[i] * p[i] > num) break;
    if (num % p[i] == 0) {
      int cnt = 0;
      while (num % p[i] == 0) {
        num /= p[i];
        cnt++;
      }
      if (pos % 2 == 0)
        solver.addedge(pos, idx, cnt);
      else
        solver.addedge(idx, pos, cnt);
      mp[pos][p[i]] = idx++;
    }
  }
  if (num != 1) {
    if (pos % 2 == 0)
      solver.addedge(pos, idx, 1);
    else
      solver.addedge(idx, pos, 1);
    mp[pos][num] = idx++;
  }
}
void merge(int a, int b) {
  if (a % 2 == 1) swap(a, b);
  for (map<int, int>::iterator iter = mp[a].begin(); iter != mp[a].end();
       ++iter) {
    int num = iter->first;
    map<int, int>::iterator iter2 = mp[b].find(num);
    if (iter2 != mp[b].end()) {
      solver.addedge(iter->second, iter2->second, 1000);
    }
  }
}
int main() {
  init();
  solver.init();
  cin >> n >> m;
  idx = n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    divide(i, a[i]);
  }
  int S = idx, T = S + 1;
  for (int i = 0; i < n; ++i) {
    if (i % 2 == 0)
      solver.addedge(S, i, 1000);
    else
      solver.addedge(i, T, 1000);
  }
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    merge(a, b);
  }
  cout << solver.solve(S, T, T + 1) << endl;
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
const int maxm = 1000000;
const int oo = 0x3f3f3f3f;
struct Edge {
  int u, v, w;
  int next;
};
struct SAP {
  int idx;
  int cur[maxn], pre[maxn];
  int dis[maxn], gap[maxn];
  int aug[maxn], head[maxn];
  Edge edge[maxm];
  void init() {
    idx = 0;
    memset(head, -1, sizeof(head));
  }
  void addedge(int u, int v, int w) {
    edge[idx].u = u;
    edge[idx].v = v;
    edge[idx].w = w;
    edge[idx].next = head[u];
    head[u] = idx++;
    edge[idx].u = v;
    edge[idx].v = u;
    edge[idx].w = 0;
    edge[idx].next = head[v];
    head[v] = idx++;
  }
  int solve(int s, int e, int n) {
    int max_flow = 0, v, u = s;
    int id, mindis;
    aug[s] = oo;
    pre[s] = -1;
    memset(dis, 0, sizeof(dis));
    memset(gap, 0, sizeof(gap));
    gap[0] = n;
    for (int i = 0; i <= n; ++i) {
      cur[i] = head[i];
    }
    while (dis[s] < n) {
      bool flag = false;
      if (u == e) {
        max_flow += aug[e];
        for (v = pre[e]; v != -1; v = pre[v]) {
          id = cur[v];
          edge[id].w -= aug[e];
          edge[id ^ 1].w += aug[e];
          aug[v] -= aug[e];
          if (edge[id].w == 0) u = v;
        }
      }
      for (id = cur[u]; id != -1; id = edge[id].next) {
        v = edge[id].v;
        if (edge[id].w > 0 && dis[u] == dis[v] + 1) {
          flag = true;
          pre[v] = u;
          cur[u] = id;
          aug[v] = min(aug[u], edge[id].w);
          u = v;
          break;
        }
      }
      if (flag == false) {
        if (--gap[dis[u]] == 0) break;
        mindis = n;
        cur[u] = head[u];
        for (id = head[u]; id != -1; id = edge[id].next) {
          v = edge[id].v;
          if (edge[id].w > 0 && dis[v] < mindis) {
            mindis = dis[v];
            cur[u] = id;
          }
        }
        dis[u] = mindis + 1;
        gap[dis[u]]++;
        if (u != s) u = pre[u];
      }
    }
    return max_flow;
  }
};
SAP solver;
bool isp[100005];
vector<long long> p;
void init() {
  memset(isp, true, sizeof(isp));
  for (long long i = 2; i < 100005; ++i) {
    if (isp[i]) {
      p.push_back(i);
      for (long long j = i * i; j < 100005; j += i) {
        isp[j] = false;
      }
    }
  }
}
int a[105];
int n, m, idx;
map<int, int> mp[105];
void divide(int pos, long long num) {
  for (int i = 0; i < p.size(); ++i) {
    if (p[i] * p[i] > num) break;
    if (num % p[i] == 0) {
      int cnt = 0;
      while (num % p[i] == 0) {
        num /= p[i];
        cnt++;
      }
      if (pos % 2 == 0)
        solver.addedge(pos, idx, cnt);
      else
        solver.addedge(idx, pos, cnt);
      mp[pos][p[i]] = idx++;
    }
  }
  if (num != 1) {
    if (pos % 2 == 0)
      solver.addedge(pos, idx, 1);
    else
      solver.addedge(idx, pos, 1);
    mp[pos][num] = idx++;
  }
}
void merge(int a, int b) {
  if (a % 2 == 1) swap(a, b);
  for (map<int, int>::iterator iter = mp[a].begin(); iter != mp[a].end();
       ++iter) {
    int num = iter->first;
    map<int, int>::iterator iter2 = mp[b].find(num);
    if (iter2 != mp[b].end()) {
      solver.addedge(iter->second, iter2->second, 1000);
    }
  }
}
int main() {
  init();
  solver.init();
  cin >> n >> m;
  idx = n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    divide(i, a[i]);
  }
  int S = idx, T = S + 1;
  for (int i = 0; i < n; ++i) {
    if (i % 2 == 0)
      solver.addedge(S, i, 1000);
    else
      solver.addedge(i, T, 1000);
  }
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    merge(a, b);
  }
  cout << solver.solve(S, T, T + 1) << endl;
  return 0;
}

```