eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Небесные коды

Небесные коды

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Станку любит космические путешествия, но он плохой разработчик программного обеспечения и никогда не будет в состоянии купить свой собственный космический корабль. Именно поэтому он готовится украсть космический корабль Петру. Существует только одна проблема - Петру заблокировал космический корабль с помощью усложненной криптосистемы на основе идентификационных номеров звезд Млечного Пути. Для взлома системы Станку должен проверить каждое подмножество четырех звезд, общий делитель номеров которых равен 1. Скверно, не так ли? К счастью, Станку удалось ограничить количество интересующих его звезд значением n, однако количество возможных подмножеств из четырех звезд все равно может оказаться слишком большим. Помогите ему найти свой номер и определить, имеется ли шанс взломать систему.

Вхідні дані

Состоит из нескольких тестов. Первая строка каждого теста содержит количество заданных интересных звезд n (1 n 10000). Вторая строка каждого теста содержит идентификационные номера интересных звезд. Каждый ИН - натуральное число, не большее 10000.

Вихідні дані

Для каждого теста вывести в отдельной строке количество подмножеств с интересующим свойством.

Приклад

Вхідні дані #1
4
2 3 4 5
4
2 4 6 8
7
2 3 4 5 7 6 8
Вихідні дані #1
1
0
34
Джерело 2008 South Eastern European Regional Programming Contest, Октябрь 16-19, Румыния, Задача B