메모리 매치

메모리 매치는 2M장의 카드를 사용하는 혼자 하는 게임이다. 각 카드의 앞면에는 1부터 M까지의 수가 하나씩 적혀 있다. 각 수 i (1 ≤ i ≤ M)에 대해, 수 i가 적힌 카드가 정확히 두 장 있다. 게임이 시작될 때 모든 카드는 섞여서 뒷면이 보이도록 탁자 위에 놓인다. 각 턴에서 두 장의 카드를 골라 앞면이 보이도록 뒤집는다. 두 카드에 적힌 수가 같으면 그 카드들은 탁자에서 제거된다. 그렇지 않으면 다시 뒷면이 보이도록 뒤집힌다(이를 미스매치라 한다). 카드를 고를 때 두 장을 동시에 뒤집을 필요는 없고, 첫 번째 카드의 수를 본 뒤에 두 번째 카드를 고를 수 있다. 게임의 목표는 최대한 적은 미스매치로 모든 카드를 제거하는 것이다.

Royce A. Mitchell은 기억력이 비범해서, 지금까지 앞면이 보이도록 뒤집은 카드의 위치와 수를 모두 기억한다. 그가 게임을 최적으로 플레이할 때 평균적으로 발생하는 미스매치 횟수의 기댓값을 계산하는 프로그램을 작성하시오.

입력은 여러 데이터셋으로 이루어진다.

각 데이터셋은 카드의 수를 나타내는 짝수 N (2 ≤ N ≤ 1000) 하나로 구성된다.

입력의 끝은 0 하나만 있는 줄로 표시된다. 이 줄은 입력의 일부가 아니며 데이터셋으로 취급해서는 안 된다.

각 데이터셋에 대해 미스매치 횟수의 기댓값을 출력한다. 오차가 10-6 이내라면 출력값의 소수 자릿수는 얼마든지 좋다.