#include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 const int p[]={,,,,,,,,,,,,,,,,,,,,,,,};

 int tot,go[],first[],next[];

 struct edge{

     int u,v;

 }e[];

 int a[],n,m,vis[][],dis[][],c[][];

 int read(){

      int t=,f=;char ch=getchar();

      while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

      while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

      return t*f;

 }

 void insert(int x,int y){

      tot++;

      go[tot]=y;

      next[tot]=first[x];

      first[x]=tot;

 }

 void add(int x,int y){

      insert(x,y);insert(y,x);

 }

 int gcd(int a,int b){

      if (b==) return a;

          else return gcd(b,a%b);

 }

 void build(int Mod){

     for (int i=;i<=n;i++) first[i]=;tot=;

     for (int i=;i<=m;i++){

         if (Mod%a[e[i].u]!=) continue;

         if (Mod%a[e[i].v]!=) continue;

         add(e[i].u,e[i].v);

     }

 }

 int spfa(int Mod){

      build(Mod);

      for (int i=;i<=n;i++)

       for (int j=;j<Mod;j++)

        dis[i][j]=0x3f3f3f3f,vis[i][j]=;

      int h=,t=;c[h][]=;c[h][]=a[]%Mod;

      vis[][]=;dis[][a[]%Mod]=a[];

      while (h<=t){

             int nowx=c[h][],nowy=c[h++][];

             for (int i=first[nowx];i;i=next[i]){

                 int pur1=go[i],pur2=((nowy*%Mod)+a[pur1])%Mod;

                 if (dis[pur1][pur2]>dis[nowx][nowy]+a[pur1]){

                     dis[pur1][pur2]=dis[nowx][nowy]+a[pur1];

                     if (vis[pur1][pur2]) continue;

                     vis[pur1][pur2]=;

                     t++;

                     c[t][]=pur1;c[t][]=pur2;

                 }

             }

             vis[nowx][nowy]=;

      }

     return dis[n][];

 }

 void solve(){

      int ans=0x3f3f3f3f;

      int sb=a[]*a[n]/gcd(a[],a[n]);

      for (int i=;i<;i++)

       if (p[i]%sb==){

         ans=std::min(ans,spfa(p[i]));

       }

      if (ans==0x3f3f3f3f) ans=-;

      printf("%d\n",ans);

 }

 int main(){

      int T=read();

      while (T--){

         n=read();m=read();

         for (int i=;i<=n;i++) first[i]=;tot=;

         for (int i=;i<=n;i++) a[i]=read();

         for (int i=;i<=m;i++){

              e[i].u=read();e[i].v=read();

         }

         solve();

      }

 }