My Code:
#include
using namespace std;
int count=0;
int GCD(long long int *arr,int n,long long int max)
{
for(int i=0;i<n;i++)
{
if(max!=arr[i] && arr[i]!=0 && arr[i]!=1 && max!=1)
{
int remainder = max%arr[i];
if(remainder==0)
{
return remainder;
}
}
else continue;
}
return -1;
}
int maxele(long long int *arr, int n)
{
long long int max=arr[0];
int index = 0;
for(int i=1;i<n;i++)
{
if(max<arr[i])
{
max = arr[i];
index = i;
}
}
return index;
}
int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
long long int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
for(int i=0;i<n-1;i++)
{
int max = maxele(arr,n);
int remain = GCD(arr,n,arr[max]);
if(remain==0)
{
count++;
arr[max] = 0;
}
else
{
arr[max]=0;
}
}
if(count==n-1)
{
cout<<-1<<endl;
}
else
{
cout<<count<<endl;
}
count =0;
}
return 0;
}