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 (Ai).

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 Ai ≤ 100.
You will be awarded another 30 points for correctly solving for Ai ≤ 10000.
The remaining 30 points will be awarded for correctly solving for Ai ≤ 1000000.

见题面

见题面