Профильная информатика:
подготовка к ЕГЭ и олимпиадам

1 2 3 4 5 6 7 8^Р 9 10 11 12 13 14 15^Р 16 17 18^Р 19 20^Р 21 22 23 24 25 26 27

Дан набор из \(N\) натуральных чисел. Необходимо определить количество пар элементов \(\left(a_{i},a_{j}\right)\) этого набора, в которых \(1\leq i<j\leq N\) и произведение элементов чётно или делится на 9.

Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел \(N\) в \(k\) раз время работы программы увеличивается не более чем в \(k\) раз. Программа считается эффективной по памяти, если память, необходимая для хранения переменных программы, не превышает одного килобайта и не увеличивается с ростом \(N\).

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

В первой строке входных данных задаётся количество чисел \(N\) (\(2\leq N\leq100\)). В каждой из последующих \(N\) строк записано одно натуральное число, не превышающее 1000.

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

	5
	3
	5
	6
	9
	2

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

	9

В приведённом наборе из 5 чисел имеются девять пар (3,6), (3,9), (3,2), (5,6), (5,9), (5,2), (6,9), (6,2) и (9,2), произведение элементов которых чётно или кратно 9.