Sky Code#1367
Stancu is an avid enthusiast of space exploration and advanced security systems. He has been given a challenging puzzle that involves deciphering a cryptographic lock based on the ID numbers of stars in the Milky Way Galaxy. To solve this puzzle, Stancu must examine every subset of four stars such that the only common divisor of their numbers is .
Fortunately, Stancu has managed to reduce the number of interesting stars to ; however, the number of possible subsets of four stars might still be too high for manual calculation. Help him count the number of such subsets with the required property.
Several test cases are given. For each test case, the first line contains the number of interesting stars (1 \leq n \leq 10000). The second line of the test case contains the list of ID numbers of the interesting stars, separated by spaces. Each ID is a positive integer not greater than . The input data terminates at the end of the file.
For each test case, the program should print one line with the number of subsets with the required property.
Example 1