1823C - Strongly Composite - CodeForces Solution

//=======================^=============================================================^=======================\\

/*

 * * *       * * *     * * * * * *       * * * * * *       * *           * *     * * * * * * *   * * * * * * * * 
 * * *       * * *   * * * * * * * *   * * * * * * * *   * * * *       * * * *   * * * * * * *   * * * * * * * * 
 * * *       * * *   * * *     * * *   * * *     * * *   * * * *       * * * *   * * * * * * *   * * * * * * * *
 * * *       * * *   * * *     * * *   * * *     * * *   * * * * *   * * * * *       * * *            * * * 
 * * *       * * *   * * *     * * *   * * *     * * *   * * *  * * * *  * * *       * * *            * * * 
 * * * * * * * * *   * * * * * * * *   * * * * * * * *   * * *   * * *   * * *       * * *            * * *  
 * * * * * * * * *   * * * * * * * *   * * * * * * *     * * *    * *    * * *       * * *            * * * 
 * * * * * * * * *   * * * * * * * *   * * * * *         * * *     *     * * *       * * *            * * *  
 * * *       * * *   * * *     * * *   * * * * * *       * * *           * * *       * * *            * * * 
 * * *       * * *   * * *     * * *   * * *  * * *      * * *           * * *       * * *            * * *   
 * * *       * * *   * * *     * * *   * * *   * * *     * * *           * * *   * * * * * * *        * * * 
 * * *       * * *   * * *     * * *   * * *    * * *    * * *           * * *   * * * * * * *        * * *  
 * * *       * * *   * * *     * * *   * * *     * * *   * * *           * * *   * * * * * * *        * * * 

*/

//=======================^=============================================================^=======================\\

#include<bits/stdc++.h>
using namespace std;

#define Author_HarMit ios_base::sync_with_stdio (0);cin.tie (0);

#define ll long long

#define fo(i,n) for(ll i=0;i<n;i++)
#define foi(i,j) for(ll i=i;i<j;i++)

#define in(n) ll n;cin>>n;
#define inn(n,k) ll n,k;cin>>n>>k;
#define arin(a,n) vl a(n);for(int i=0; i<n; i++)cin>>a[i];
#define strin(s) string s;cin>>s;

#define cy printf("YES\n")
#define cn printf("NO\n")
#define cm printf("-1\n")
#define out(n) cout<<n<<endl;
#define nl printf("\n");

#define pb emplace_back
#define mp make_pair
#define ppb pop_back

#define F first
#define S second

#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))

#define PI 3.1415926535897932384626
const ll mod = 1e9 + 7;

typedef pair < ll, ll > pl;
typedef vector < ll > vl;
typedef map < ll, ll > mll;
typedef vector < pl > vpl;

//=======================^=============================================================^=======================\\

ll power(ll x,ll y)
{
    ll temp;
    if (y == 0) return 1;
        
    temp = power(x, y / 2);
    
    if (y % 2 == 0) return temp * temp;
        
    else return x * temp * temp;
}

void solve(){
    
    ll m,n;
  cin >> m;
 
  vl a (m);
  mll mi;
 
  fo (j, m)
  {
    cin >> a[j];
    
    n = a[j];
 
    while (n % 2 == 0)
      {
	mi[2]++;
	n = n / 2;
      }
 
    for (int i = 3; i <= sqrt (n); i = i + 2)
      {
	while (n % i == 0)
	  {
	    mi[i]++;
	    n = n / i;
	  }
      }
    if (n > 2)
      mi[n]++;
  }
 
   auto it = mi.begin();
   ll extra = 0,ans=0;
   
   while(it != mi.end()){
       
       ans += (it->S)/2;
       extra += (it->S)%2;
       
       it++;
   }
   
   ans += extra/3;
   
   cout<<ans<<endl;
    
}

signed main ()
{
  Author_HarMit
 
  int t = 1;
  cin >> t;
  while (t--)
    {

      solve ();
    }

  return 0;
}