Cho hai số nguyên ~a, b~ thỏa ~2 \le a, b \le 5~. Thực hiện phép ~a^b~ và loại bỏ phần tử trùng nhau ta có dãy số: ~4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125~.

Cho trước số ~n~, hãy tính số phần tử phân biệt nhau của ~a^b~ với ~2 \le a, b \le n~.

Input

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

Output

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

Samples

Sample Input 1

5

Sample Output 1

15