#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+10;
class dsu 
{
public:
    vector<ll> parent,size;
    dsu(ll n) {
        parent.resize(n + 1);
        size.resize(n + 1,1);
        for (ll i = 0; i <= n; i++) parent[i] = i;
    }

    ll par(ll node) {
        if (node == parent[node])
            return node;
        return parent[node]=par(parent[node]);
    }
       void usize(ll u,ll v) {
        ll ulp_u=par(u);
        ll ulp_v=par(v);
        if (ulp_u == ulp_v) return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};
bool prime[N]; 
void pre()
{
    memset(prime,true,sizeof(prime));
    prime[1]=0;
    for(ll i=2;i*i<=N;i++)
    {
        if(prime[i]==1)
        {
            for(ll j=i*i;j<=N;j+=i)
                prime[j]=0;
        }
   }
}
signed main()
{   
    pre();
    ll n; cin>>n;
    dsu obj(n+1);
   vector<vector<ll>>g(n+1);
   for(ll i=1;i<n;i++)
   {
    ll a,b; cin>>a>>b;
    if(prime[a]==1 && prime[b]==1) continue;
    else if(prime[a]==1) g[a].push_back(b);
    else if(prime[b]==1) g[b].push_back(a);
    else obj.usize(a,b);
   }
   ll ans=0;
   for(ll i=1;i<=n;i++)
   {
    if(prime[i])
    {
      ll curr=1;
      for(auto rel:g[i]) curr+=obj.size[obj.par(rel)];
      for(auto rel:g[i])
      {
        ll ex=obj.size[obj.par(rel)];
        ans+=ex*(curr-ex);
        curr-=ex;
      }
    }
   }
   cout<<ans<<endl;
}

SELECT order_id, product_id, buyer
FROM quantity
WHERE quantity_ordered = ANY (SELECT 6)
ORDER BY buyer ASC;

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll solve(vector<ll>&a)
{
    ll n=a.size();
    ll ans=0;
    unordered_map<ll,ll>mpp;
    for(auto it:a) mpp[it]++;
    ll i=3;
    vector<ll>t;
    while(i<=pow(3,21))
    {
        t.push_back(i);
        i*=3;
    }
    for(ll i=0;i<n;i++)
    {
        for(auto it:t)
        {
            if(it>=a[i] && mpp.find(it-a[i])!=mpp.end()) ans+=mpp[a[i]]*mpp[it-a[i]];
            
        }
        mpp.erase(a[i]);
    }
    return ans;
   
}
signed main()
{   
        ll n; cin>>n;
        vector<ll>a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        cout<<solve(a)<<endl;  
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>solve(vector<ll>&a,ll n,ll k)
{
   
    ll i=0; 
    while(k) 
    {
        if(a[i]!=0) 
        {
            a[i]--;
            k--;
        }
        i=(i+1)%n;
    }
    return a;
}
signed main()
{   
        ll n,k; cin>>n>>k;
        vector<ll>a(n);
        for(ll i=0;i<=n-1;i++) cin>>a[i];
        auto ans=solve(a,n,k);
        for(auto it:ans) cout<<it<<" ";
        cout<<endl;
    }

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll solve(vector<ll>&a)
{
    ll n=a.size();
    priority_queue<ll>pq;
    ll mini=LONG_MAX;
    for(auto it:a)
    {
        if(it%2) it*=2;
        mini=min(mini,it);
        pq.push(it);
    }
    ll ans=LONG_MAX;
    while(pq.top()%2==0)
    {
        auto it=pq.top();
        pq.pop();
        ans=min(ans,it-mini);
        mini=min(mini,it/2);
        pq.push(it/2);
    }
    return min(ans,pq.top()-mini);
}
signed main()
{   
    ll t; cin>>t;
    while(t--)
    {
        ll n; cin>>n;
        vector<ll>a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        cout<<solve(a)<<endl;
    }    
}