팩토리얼 곱에서 잘라내기

양의 정수 $n$의 팩토리얼 $n!$은 $1$부터 $n$까지의 모든 정수의 곱입니다. 즉 $n! = 1 \times 2 \times 3 \times \cdots \times n$ 입니다.

처음 $k$개의 팩토리얼의 곱 $1! \times 2! \times 3! \times \cdots \times k!$ 을 생각합니다. 이 곱에서 팩토리얼 몇 개를 통째로 골라 곱셈에서 제외할 수 있습니다. 남은 팩토리얼들의 곱이 어떤 정수의 완전제곱수(제곱수)가 되도록 만들려고 합니다.

이때 제외해야 하는 팩토리얼의 최소 개수를 구하세요.

정수 $k$가 한 줄에 주어집니다. ($2 \le k \le 500$)

남은 팩토리얼들의 곱이 완전제곱수가 되도록 하기 위해 제외해야 하는 팩토리얼의 최소 개수를 한 줄에 출력합니다.