F. Four Divisorstime limit per test10 secondsmemory limit per test768 megabytesinputstandard inputoutputstandard outputIf an integer a is divisible by another integer b, then b is called the divisor of a.For example: 12 has positive 6 divisors. They are 1, 2, 3, 4, 6 and 12.Let’s define a function D(n) — number of integers between 1 and n (inclusive) which has exactly four positive divisors.Between 1 and 10 only the integers 6, 8 and 10 has exactly four positive divisors. So, D(10) = 3.You are given an integer n. You have to calculate D(n).InputThe only line contains integer n (1 ≤ n ≤ 1011) — the parameter from the problem statement.OutputPrint the only integer c — the number of integers between 1 and n with exactly four divisors.ExamplesInput10Output3Input20Output5
Input10
Output3
['data structures', 'dp', 'math', 'number theory', 'sortings', 'two pointers', '*2400']