https://www.codechef.com/viewsolution/30865990
#include<bits/stdc++.h>
#define ll long long int
#define pll pair <ll,ll>
#define vll vector
#define vpl vector
#define s second
#define f first
using namespace std;
ll temp;
vll primes;
vpl vec[10001];
void f()
{
ll arr[10001]={0};
for(ll i=2;i<10001;i++)if(!arr[i]){primes.push_back(i);for(ll j=i;j<10001;j+=i)if(!arr[j])arr[j]=i;}
for(ll i=2;i<10001;i++)
{
ll n=i,c;
while(n>1)
{
temp=arr[n];
c=0;
while(n%temp==0)n/=temp,++c;
vec[i].push_back(make_pair(temp,c));
}
}
}
vpl lcm(vpl a,vpl b)
{
ll n=a.size(),m=b.size();
vpl z;
for(ll i=0,j=0;i<n || j<m;)
{
if(i<n && j<m){
if(a[i].f==b[j].f)z.push_back(make_pair(a[i].f,max(a[i].s,b[j].s))),i++,j++;
else if(a[i].f<b[j].f)z.push_back(a[i]),i++;
else z.push_back(b[j]),j++;
}
else if(i<n)z.push_back(a[i]),i++;
else if(j<m)z.push_back(b[j]),j++;
else break;
}
return z;
}
ll power(ll n,ll m)
{
if(m==0)return 1;
ll z=power(n,m>>1);
z*=z;
if(m&1)z*=n;
return z;
}
ll hcf(ll a,vpl b)
{
ll n=vec[a].size(),m=b.size();
ll ans=1;
for(ll i=0,j=0;i<n && j<m;)
{
if(vec[a][i].f==b[j].f)ans*=power(vec[a][i].f,min(vec[a][i].s,b[j].s)),i++,j++;
else if(vec[a][i].f<b[j].f)i++;
else j++;
}
return a/ans;
}
vpl find(ll arr[],ll start,ll end)
{
if(start==end)return vec[arr[start]];
ll mid=(start+end)>>1;
return lcm(find(arr,start,mid),find(arr,mid+1,end));
}
void solve()
{
ll n,m;
cin>>n>>m;
ll arr[n];
vpl z;
for(ll i=0;i<n;i++)cin>>arr[i];
z=find(arr,0,n-1);
ll maxy=1;
ll multi=1;ll ans=1;
ll p=primes.size();
for(ll i=2;i<=m;i++)
{
multi=hcf(i,z);
if(multi>maxy)maxy=multi,ans=i;
}
cout<<ans<<"\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
f();
int t;
cin>>t;
while(t–)solve();
return 0;
}