Задача . G. Скибидус и ложь

Скибидус был похищен инопланетянами с Амога! Скибидус пытается выкрутиться, но инопланетяне с Амога не верят ему. Чтобы доказать, что он не врет, инопланетяне с Амога попросили его решить эту задачу:

Целое число \(x\) считается полупростым, если его можно записать в виде \(p \cdot q\), где \(p\) и \(q\) — (не обязательно разные) простые числа. Например, \(9\) является полупростым, так как его можно записать как \(3 \cdot 3\), а \(3\) является простым числом.

Скибидусу был дан массив \(a\), содержащий \(n\) целых чисел. Он должен сообщить количество пар \((i, j)\) таких, что \(i \leq j\) и \(\operatorname{lcm}(a_i, a_j)\)\(^{\text{∗}}\) является полупростым.