Задание 27 из ЕГЭ по информатике: задача 35

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 39.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 39.

Пример входных данных:

4
2
6
13
39

Пример выходных данных для приведённого выше примера входных данных: 4

Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·13, 2·39, 6·13, 6·39, 13·39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 39 делятся 3 произведения (2·39=78; 6·13=78; 6·39=234; 13·39=507).