Number of Factors

Alice has learnt factorization recently. Bob doesn't think she has learnt it properly and hence he has decided to quiz her. Bob gives Alice a very large number and asks her to find out the number of factors of that number. To make it a little easier for her, he represents the number as a product of N numbers. Alice is frightened of big numbers and hence is asking you for help. Your task is simple. Given N numbers, you need to tell the number of distinct factors of the product of these N numbers.

Input:

First line of input contains a single integer T, the number of test cases.

Each test starts with a line containing a single integer N.
The next line consists of N space separated integers (A_i).

Output:

For each test case, output on a separate line the total number of factors of the product of given numbers.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 10
2 ≤ Ai ≤ 1000000

Example:

Input:

3
3
3 5 7
3
2 4 6
2
5 5

Output:

8
10
3

Scoring:

You will be awarded 40 points for correctly solving for A_i ≤ 100.

You will be awarded another 30 points for correctly solving for A_i ≤ 10000.

The remaining 30 points will be awarded for correctly solving for A_i ≤ 1000000.

********************************************editorial**************************************************************

Problem:

You are given a very large number represented as a product of N numbers. Given this number representation, you need to find the number of distinct factors of the original number which is formed by the product of given N numbers.

Quick Explanation:

We can factorize each one of the N given numbers into its prime factors. Then we find the number of occurrences of each prime factor, say they are a1, a2,...aK, if we have K distinct prime factors. Our answer is simply: (a1+1)(a2+1)(...)*(aK+1).

Detailed Explanation:

This problem relies on some knowledge of divisor function. Divisor functions returns the number of positive and distinct divisors of a number. Let's call it d(x).

• Some properties of the divisor function:
  We now look into some important properties of the divisor function:
  For a prime number p, we have d(p) = 2, as there are only two numbers which divide a prime number:1 and itself.
  Now, it's a known fact that this function is multiplicative but not completely multiplicative. This means that if two numbers, say, a and b are there such that gcd(a, b) = 1, then the following holds:  d(a*b) = d(a)*d(b).

This allows us to deduce the important relationship, that is the key of solving this problem:

For a prime number, p, we have: d(p^n) = n+1.

Now, it's easy to understand that all we need to do is to factorize all the N given numbers into its prime factors, and, for each prime factor we also need to count how many times it appears (that is, we need to know the exponent of each prime factor).

Once we have this count with us (which can be done using integer factorization and for example, the set and map data structures, one to guarantee uniqueness of the factors and the other to save the number of occurences for each unique prime factor), all we need to do is to multiply all these numbers plus one together and we will obtain our answer.

As an example, consider the number:

504 = 2^3 * 3^2 * 7^1

The number of distinct divisors of 504 is then (3+1) * (2+1) * (1+1) = 24.

Applying this process to all numbers yields the answer to the problem :)

**************************************CODE***********************************************************************************

#include<iostream>

using namespace std;

 typedef  int lli;

 #include<bits/stdc++.h>

lli prime[1000000];

lli base[1000000];

 int read_int(){

char r;

bool start=false,neg=false;

int ret=0;

while(true){

r=getchar();

if((r-'0'<0 || r-'0'>9) && r!='-' && !start){

continue;

}

if((r-'0'<0 || r-'0'>9) && r!='-' && start){

break;

}

if(start)ret*=10;

start=true;

if(r=='-')neg=true;

else ret+=r-'0';

}

if(!neg)

return ret;

else

return -ret;

}

 int pri()

  {

  //cout<<" prime "<<endl;

   for(int i=2;i<1011;i++)

    {

     if(!prime[i])

       {

        for(  int j=2;j*i<=1000001;j++)

         {

         //  cout<<prime[i]<<" "<<j<<endl;

            prime[j*i]=1;

  }

}

 

}

// cout<<" here "<<endl;

 int pt=0;

 for(int i=2;i<1000001;i++)

  {

   if(!prime[i]) base[pt++]=i; 

  }

 //  cout<<" gone "<<endl;

return 0;

  }

  

  

 int fact(map<lli,lli> &mymap,lli num)

  {

  int kk=10;

  for(int i=0;;i++)

   {

   // if(kk--==0) return 0; 

    if(num==0 || num==1)return 0;

     else

      {

      lli div=base[i];

      //if(div==0) return 0;

      int k=10;

     

       while(num%div==0 && num!=0 && num!=1)

        {

       // if(k--==0) return 0;

        // cout<<num<<endl;

         mymap[div]++;

         num/=div;

         if(num==0) return 0;

 }

  }

}

  }

  

  

 int main()

  {

  pri();

   

  int t;

  // cin>>t;

  t=read_int();

   while(t--)

    {

     

    int n;

   // scanf("%d",&n);

   n=read_int();

     int arr[n];

      map<lli,lli> mymap;

      for(int i=0;i<n;i++)

       {

        int a;

          //scanf("%d",&a);

          a=read_int();

          fact(mymap,a);

           }

           map<lli,lli> ::iterator it;

            lli ans=1;

           for(it=mymap.begin();it!=mymap.end();it++)

            {

            //cout<<" falcul"<<ans<<endl;

            ans*=(it->second+1);

}

           

             cout<<ans<<endl;

             

   

  }

  return 0;

}