Совсем недавно Миша на сборах от ИТ-кампуса «НЕЙМАРК» изучил новую для себя тему — алгоритм Евклида.

Он был немного удивлен, когда понял, что $$$a \cdot b = lcm(a, b) \cdot gcd(a, b)$$$, где $$$gcd(a, b)$$$ — наибольший общий делитель (НОД) чисел $$$a$$$ и $$$b$$$, а $$$lcm(a, b)$$$ — наименьшее общее кратное (НОК). Миша подумал, что если есть произведение НОК и НОД, то будет не лишним рассмотреть и частное — $$$F(a,b)=\frac{lcm(a, b)}{gcd(a, b)}$$$.

Для примера он взял $$$a = 2$$$ и $$$b = 4$$$, посчитал $$$F(2, 4) = \frac{4}{2} = 2$$$ и получил простое число (число простое, если у него ровно 2 делителя)! Теперь он считает $$$F(a, b)$$$ интересным соотношением, если $$$a \lt b$$$ и $$$F(a, b)$$$ — простое число.

Поскольку Миша только недавно начал изучать теорию чисел, то ему нужна ваша помощь, чтобы посчитать — а сколько существует различных пар чисел $$$a$$$ и $$$b$$$ таких, что $$$F(a, b)$$$ — интересное соотношение и $$$1 \leq a \lt b \leq n$$$.