그래프 매칭

그래프 이론에서 매칭(또는 독립 간선 집합)은 서로 공통 정점을 가지지 않는 간선들의 집합이다.

그래프 $G = (V, E)$가 주어졌을 때, 간선 집합 $M$이 $G$의 매칭이려면 $M \subseteq E$이면서 $M$에 속한 어떤 두 간선도 같은 정점을 공유하지 않아야 한다. 공집합도 하나의 매칭으로 센다.

사이클 그래프 $C_n$ ($n \ge 3$)은 정점 집합이 ${1, 2, \dots, n}$인 단순 무방향 그래프로, 간선 집합은 $E(C_n) = {{a, b} \mid a - b \equiv \pm 1 \pmod n}$이다. 즉 $n$개의 정점이 이웃한 정점끼리 연결되어 하나의 고리를 이루며, 모든 정점의 차수가 $2$인 $2$-정규 그래프이고 간선의 수는 정확히 $n$개이다.

사이클 그래프 $C_n$의 매칭의 개수를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$ 하나로 주어지며, 한 줄에 하나씩 입력의 끝까지 계속된다. ($3 \le n \le 10000$)

각 테스트 케이스마다 $C_n$의 매칭의 개수를 한 줄에 하나씩 출력한다.