                              //ABHISHEK AGRAWAL,BIT mesra//                    
                      //Newbie......You have to be odd to be no. ONE :)//
//Author: Abhishekagrawal 
//Date: 15/03/2021 
//Time: 04:36:03
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define fl float
#define vll vector<ll>
#define pii pair<int,int>
#define vpll vector<pair<ll,ll>>
#define pb push_back
#define f first
#define s second
#define mll map<ll,ll>
#define mp make_pair
#define sp(n) fixed<<setprecision(n)
#define mod (ll)1000000007
#define sortv(v) sort(v.begin(),v.end())
#define INF (ll)(1e15)
#define loop(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define rloop(n,i) for(int i=n-1;i>=0;i--)
#define sorta(a) sort(a,a+n,greater<ll>())
#define countone(n) __builtin_popcount(n)
#define numoftrailzero(n) __builtin_ctz(n)
#define maxpowoftwo(n) __builtin_clz(n)
#define leastindexwithone(n)  __builtin_ffs(n)
#define what_is(x) cerr << #x << " is " << x << endl;
#define pfv(v) cout<<v.size()<<"\n";loop(i,v.size()) cout<<v[i]<<" ";cout<<"\n";
#define pv(v) loop(i,v.size()) cout<<v[i]<<" ";
#define all(v) v.begin(),v.end()
#define mset(dp,val) memset(dp,val,sizeof(dp))
ll test,n;ll sum,ans;
void the_happiest_place_on_earth()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
  #ifdef ENABLE_FILE_IO
    freopen("out.txt", "r", stdin);
    freopen("out1.txt", "w", stdout);
  #endif      
} 
// bool comp(const pair<ll,ll> &a, const pair<ll,ll> &b){
//   if(a.s+2*a.f==b.s+2*b.f) return a.f>b.f;
//   return (a.s+2*a.f>b.s+2*b.f);
// }
const int N=200040;ll a[N],b[N],c[N],par[N],Size[N],present[N],color[N];
ll sieve_spf[1000110];
ll n1=1000000;
void Sieve_spf(){
 loop(i,n1) sieve_spf[i]=i;
  sieve_spf[0]=-1;
  sieve_spf[1]=1;
  for(int i=2;i<n1;i+=2) sieve_spf[i]=2;
  for(ll i=3;i<n1;i+=2){
    if(sieve_spf[i]==i){
      for(ll j=(i*i);j<n1;j+=i){
        if(sieve_spf[j]==j) sieve_spf[j]=i;
      }
    }
  }
}
vll v;
void dfs(int i, ll j){
	if(i==15){
		for(int k=0; k<n; ++k)
			if(__gcd(a[k],j)<2) return;
		ans=min(ans,j); return;
	}
	dfs(i+1,j);
	dfs(i+1,j*v[i]);
}
void testcase(){
  cin>>n;
  loop(i,n) cin>>a[i];
  ans=LLONG_MAX;
  dfs(0,1);
  cout<<ans<<"\n";
  return;
}

int main(){
  the_happiest_place_on_earth();
  // Today's thought: Push yourself,because no one else is going to do it for you.
  // Things are not always #000000 and #FFFFFF
  // g++ -o a BB.cpp -DENABLE_FILE_IO;./a
  // g++ -std=c++17 -Wshadow -Wall -g -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -o a file_name.cpp;./a
  test=1;int t=0;
  Sieve_spf();
  loop1(i,50){
    if(sieve_spf[i]==i&&i!=1) v.pb(i);
  }
  // cin>>test;  
  while(test--){
    //cout<<"Case #"<<++t<<": ";
    testcase();
  } 
  cerr << "Time : " << 1000 *((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
  return 0;
}
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
// avoid unordered_map and unordered_set!!!
#include <vector>
#include <utility>

using namespace std;

using i64 = int64_t;
using u64 = uint64_t;
using i32 = int32_t;
using pi64 = pair<i64, i64>;

#define vec vector
#define let const
#define DRi64(x) i64 x; cin >> x;
#define DRS(x) string x; cin >> x;
#define DRVi64(v, n) vec<i64> v(n); { for (i64 i = 0; i < n; ++i) { cin >> v[i]; }}
#define DRpi64(x) pi64 x; cin >> x.first >> x.second;

#ifdef DEBUG
#define P(x) cerr << x << "\n"
#else
#define P(x)
#endif

constexpr i64 MAXN = 3*100*1000LL+5LL;
constexpr i64 MOD = 1000000007LL;
constexpr i64 INF64 = MOD * MOD;

bool
dfs(const i64 u, const i64 p, vec<i64>& colour, const i64 mask, const vec<vec<i64>>& adj)
{
    bool ok = true;
    for (let i64 nbr : adj[u])
    {
        if (nbr == p)
        {
            continue;
        }
        if (mask & (1LL<<nbr))
        {
            continue;
        }

        if (colour[nbr] < 0)
        {
            colour[nbr] = !colour[u];
            ok &= dfs(nbr, u, colour, mask, adj);
        }
        if (colour[nbr] == colour[u])
        {
            return false;
        }
    }
    return ok;
}

int
main()
{
    ios_base::sync_with_stdio(false);
    // fast io: see 1423K
    cin.tie(nullptr);
    cout.tie(nullptr);

    DRi64(N); DRi64(M);
    vec<vec<i64>> adj(N);
    for (i64 i = 0; i < M; ++i)
    {
        DRi64(A); DRi64(B);
        A--, B--;
        adj[A].push_back(B);
        adj[B].push_back(A);
    }

    i64 ways = 0;
    for (i64 mask = 0; mask < (1LL << N); ++mask)
    {
        bool bad = false;
        for (i64 b = 0; !bad && b < N; ++b)
        {
            if ((1LL<<b) &  mask)
            {
                for (let i64 nbr : adj[b])
                {
                    bad |= (mask & (1LL<<nbr));
                }
            }
        }
        if (bad)
        {
            continue;
        }
        P(bitset<4>(mask));
        i64 subways = 1;
        // how many  ways to colour the uncoloured vertices?
        vec<i64> colour(N, -1);
        for (i64 b = 0; b < N; ++b)
        {
            if ((1LL<<b) & mask)
            {
                continue;
            }
            if (colour[b] >= 0)
            {
                continue;
            }
            colour[b] = 0;
            let bool subproblem = dfs(b, -1, colour, mask, adj);
            bad |= subproblem == 0;
            // indepent subproblems -- different components
            subways *= 2;
        }
        ways += !bad * subways;
    }
    cout << ways << "\n";

    return 0;
}
