Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2274
Triples

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Recently he is fascinated with prime number, finding that triples that is relatively prime within each pair or not relatively prime within each pair rather interesting, however, to put all this cases in statistics is not a fair of ease.

Are you outstanding programmers pleased to offer him some help?

Input

This problem consists of several test cases. Each case consists of two lines, the first line is an integer N (3<=N<=500), then N different positive integers follows in the second line, which are in the range [2, 1000000].

Output

For each test case you should just output a single number perline, indicating the number of triples you have found.

Sample Input

5
2 3 4 6 5

Sample Output

3

Note:
(2, 3, 5) is a triple, for GCD(2, 3) == 1 && GCD(2, 5) == 1 && GCD(3, 5) == 1.
(2, 4, 6) is also a triple, for GCD(2,4) > 1 && GCD(2, 6) > 1 && GCD(4, 6) > 1.
(2, 4, 5) is not a triple, for GCD(2,4) > 1 but GCD(2, 5) == 1.

Author: LIU, Yaoting
Source: ZOJ Monthly, December 2004
Submit    Status