Cutting Out of Factorials

Interview

Time limit1sMemory limit128 MB

Summary

Given k from 2 to 500, remove the fewest of 1!, 2!, ..., k! so the remaining product is a perfect square, and report that count.

Level: Medium6 of 10
Topics: Math, Number theory, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

The factorial of a positive integer $n$ , written $n!$ , is the product of all integers from $1$ to $n$ : $n! = 1 \times 2 \times 3 \times \cdots \times n$ .

Consider the product of the first $k$ factorials, $1! \times 2! \times 3! \times \cdots \times k!$ . You may remove some of these factorials entirely from the product. The goal is to make the product of the remaining factorials a perfect square (the square of some integer).

Determine the minimum number of factorials that must be removed so that the product of the remaining factorials is a perfect square.

Input

A single line contains the integer $k$ ( $2 \le k \le 500$ ).

Output

Output a single line containing the minimum number of factorials that must be removed so that the product of the remaining factorials is a perfect square.

Examples4

Example 1
Input
```
4
```
Expected output
```
1
```
Example 2
Input
```
6
```
Expected output
```
2
```
Example 3
Input
```
2
```
Expected output
```
1
```
Example 4
Input
```
7
```
Expected output
```
3
```