Triples

Time Limit: 1 Second    Memory Limit: 32768 KB

alsomagic is crazy about figures.

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

Submit

Source: ZOJ Monthly, December 2004