Козак Вус і домноження
Козак Вус досліджував дуже цікаву операцію: домноження числа на будь-який дільник. Наприклад, число він може домножити на , , або і отримати , , або відповідно.
Далі він навчився робити таку операцію з масивом чисел , який складається з чисел. Для цього він просто кожне число масиву множить на будь-який дільник . Винайдену операцію він назвав «домноження масиву».
Одразу після цього Вус вирішив називати пару чисел «гарною», якщо виконуються наступні умови:
.
Можна виконати не більше «домножень масиву» таким чином, щоб усі числа стали однаковими.
Ваша ж задача "— для заданого масиву знайти кількість «гарних» пар чисел. Нещодавно Козак з'ясував, що всі прості дільники чисел з масиву менші за . Нагадаємо, що простим називається натуральне число, яке має рівно два різних натуральних дільники.
Вхідні дані
Перший рядок містить три цілі числа , та (, , ) "— кількість елементів в масиві, максимальна кількість операцій «домноження масиву» та номер блоку, до якого належить тест відповідно.
Другий рядок містить цілих чисел () "— елементи масиву . Гарантується, що немає такого числа, яке ділиться на просте число більше за .
Вихідні дані
Виведіть одне число "— кількість «гарних» пар.
Приклади
Примітка
Пояснення до першого прикладу:
Розглянемо всі «гарні» пари:
Пари , , , та «гарні» навіть без «домножень масиву».
: домножуємо на , а на .
: домножуємо на , на , а на .
: домножуємо на , а на .
: домножуємо на , а на .
Оцінювання
( балів) .
( балів) .
( балів) .
( балів) .
( балів) .
( балів) , усі , де — невід'ємне ціле число.
( балів) , усі , де — невід'ємне ціле число.
( балів) , усі , де та — невід'ємні цілі числа.
( балів) , усі , де та — невід'ємні цілі числа.
( балів) .
( балів) .
( балів) .