Рассмотрим некоторое положительное целое число \(x\). Его разложение на простые имеет вид \(x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots\)
Назовем число \(x\) изящным, если наибольший общий делитель последовательности \(k_1, k_2, \dots\) равен \(1\). Например, числа \(5 = 5^1\), \(12 = 2^2 \cdot 3\), \(72 = 2^3 \cdot 3^2\) изящные, а числа \(8 = 2^3\) (\(GCD = 3\)), \(2500 = 2^2 \cdot 5^4\) (\(GCD = 2\)) — нет.
Посчитайте количество изящных чисел от \(2\) до \(n\).
В каждом тесте содержится несколько значений \(n\), для каждого из них необходимо решить задачу независимо.