codeforces#P1609C. Complex Market Analysis
Complex Market Analysis
Description

While performing complex market analysis William encountered the following problem:
For a given array of size and a natural number , calculate the number of pairs of natural numbers which satisfy the following conditions:
- .
- Product is a prime number.
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.
Each test contains multiple test cases. The first line contains the number of test cases (). Description of the test cases follows.
The first line of each test case contains two integers and , the number of items in the array and number , respectively.
The second line contains integers , the contents of the array.
It is guaranteed that the sum of over all test cases does not exceed .
For each test case output the answer in the following format:
Output one line containing the number of pairs of numbers which satisfy the conditions.
Input
Each test contains multiple test cases. The first line contains the number of test cases (). Description of the test cases follows.
The first line of each test case contains two integers and , the number of items in the array and number , respectively.
The second line contains integers , the contents of the array.
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case output the answer in the following format:
Output one line containing the number of pairs of numbers which satisfy the conditions.
Samples
Note
In the first example test case two pairs satisfy the conditions:
- , for which the product is: which is a prime number.
- , for which the product is: which is a prime number.
In the second example test case there are no pairs that satisfy the conditions.
In the third example test case four pairs satisfy the conditions:
- , for which the product is: which is a prime number.
- , for which the product is: which is a prime number.
- , for which the product is: which is a prime number.
- , for which the product is: which is a prime number.
In the fourth example test case there are no pairs that satisfy the conditions.
In the fifth example test case five pairs satisfy the conditions:
- , for which the product is: which is a prime number.
- , for which the product is: which is a prime number.
- , for which the product is: which is a prime number.
- , for which the product is: which is a prime number.
- , for which the product is: which is a prime number.
In the sixth example test case there are no pairs that satisfy the conditions.