저금통
시간 제한1초메모리 제한128 MB
두 저금통을 (1,1)에서 (N,N)까지 채우는 순서를 자유롭게 선택할 때, 두 값을 이어붙인 수가 소수가 되는 상태의 최대 개수를 구합니다.
문제
태석은 저금통 두 개를 가지고 있다. 처음에는 두 저금통에 각각 1원이 들어 있다. 태석은 하루에 정확히 한 저금통을 골라 1원을 넣고, 두 저금통이 모두 N원이 되면 저금을 멈춘다.
어떤 상태에서 첫 번째 저금통의 금액이 a원, 두 번째 저금통의 금액이 b원일 때, a와 b를 이 순서대로 이어 붙여 만든 정수가 소수이면 그 상태를 좋은 상태라고 하자. 처음 상태 (1, 1)에서 만들어지는 11은 세지 않는다.
태석은 돈을 넣는 순서를 자유롭게 정할 수 있다. 가능한 모든 순서 중 좋은 상태가 나타나는 횟수를 최대로 만들 때, 그 최대 횟수를 구하라.
입력
첫째 줄에 정수 N이 주어진다. (1 <= N <= 999)
출력
좋은 상태가 나타나는 횟수를 최대로 만들었을 때의 값을 출력한다.