Рассмотрим некоторое положительное целое число \(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\), для каждого из них необходимо решить задачу независимо.
Выходные данные
Выведите \(T\) строк — в \(i\)-й строке должно содержаться количество изящных чисел от \(2\) до \(n_i\).
Примечание
Приведен список не изящных чисел до \(10\):
- \(4 = 2^2, GCD = 2\);
- \(8 = 2^3, GCD = 3\);
- \(9 = 3^2, GCD = 2\).
Для остальных \(GCD = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
2
72
10
|
2
1
61
6
|