재귀적 팰린드롬 파티션

양의 정수 N의 파티션은 양의 정수로 이루어진 수열이며, 모든 원소의 합이 N인 것이다. 보통 각 원소 사이에 +를 넣어 나타낸다.

파티션을 앞에서 읽은 순서와 뒤에서 읽은 순서가 같으면 팰린드롬 파티션이라고 한다.

길이가 m인 파티션에서 왼쪽 절반은 처음 floor(m / 2)개의 원소이고, 오른쪽 절반은 마지막 floor(m / 2)개의 원소이다. 길이가 홀수이면 가운데 원소는 어느 절반에도 포함되지 않는다.

재귀적인 팰린드롬 파티션은 다음 조건을 만족하는 파티션이다.

1. 전체 파티션이 팰린드롬이다.
2. 왼쪽 절반과 오른쪽 절반이 비어 있거나, 각각 재귀적인 팰린드롬 파티션이다.

N 자체로 이루어진 파티션과 1을 N개 나열한 파티션은 항상 조건을 만족한다. 양의 정수 N이 주어질 때, N의 재귀적인 팰린드롬 파티션 개수를 구하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 <= T <= 1,000)

다음 T개의 줄에는 양의 정수 N이 하나씩 주어진다. (1 <= N <= 1,000)

각 테스트 케이스마다 N의 재귀적인 팰린드롬 파티션 개수를 한 줄에 하나씩 출력한다.