Số nhỏ nhất được biểu diễn bằng công thức ~p^2 + q^3 + r^4~ là số ~28~ với ~p, q, r~ là số nguyên tố, cụ thể là ~28 = 2^2 + 2^3 + 2^4~.

Người ta thống kê có ~4~ số như vậy nhỏ hơn ~50~ gồm: ~28, 33, 47, 49~.

Cho trước số nguyên ~n~, tìm có bao nhiêu số nhỏ hơn hoặc bằng ~n~ được biểu diễn như trên.

Input

Dòng duy nhất chứa số nguyên ~n~ thỏa ~1 \le n \le 10^7~.

Output

In ra số phần tử cần tính.

Samples

Sample Input 1

50

Sample Output 1

4