hi guys

for this question https://codeforces.me/gym/104493/problem/B

my solution is exceeding time limit

include<bits/stdc++.h>

using namespace std;

define ll long long

define ull unsigned long long

bool isPrime(ll num) { if(num<=1) return false; for(ll i=2; i*i<=num; ++i) { if(num%i==0) return false; } return true; }

int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll t; cin>>t; while(t--) { ll n,q; cin>>n>>q; vectorvec(n); ll max=0; for(ll i=0; i<n; ++i) { cin>>vec[i]; if(vec[i]>max) { max=vec[i];}}

vector<ll>prime;
    for(ll num=2; num<=max; ++num)
  {
    if(isPrime(num))
    {
        prime.push_back(num);
    }
  }


    while(q--)
    {
        ll l,r; cin>>l>>r;
        vector<ll>mec;
        for(ll i=l-1; i<=r-1; ++i) { mec.push_back(vec[i]);}

        ll max_index=0;
        ll length=mec.size();
        ll count=0;

     while(length>0)
     {
        ll maxi=0;
        for(ll j=0; j<mec.size(); ++j)
        {
            if(mec[j]>maxi) {maxi=mec[j]; max_index=j;}
        }
        for(ll k=prime.size()-1; k>=0; --k)
        {
            if(maxi%prime[k]!=0) {continue;}
            else{
                mec[max_index]=maxi/prime[k];
                ++count;
                break;
                }
        }
        if(mec[max_index]==1) { --length;}
     }
     cout<<count<<"\n";


    }


}

}