偶数的划分1（划分成偶数）

题目描述

给定一个正偶数n，n=2×k，k为整数且k>0，n可以表示成若干个正偶数之和，例如：6 = 4 + 2。正偶数n的这种表示称为n的划分，n的不同划分的个数记为P1(n)。例如，6有以下3种不同的划分，因此：P1(6) = 3。对于给定的正偶数n，求解P1(n)并输出。

6 = 6
6 = 4 + 2
6 = 2 + 2 + 2

输入描述

第1行为正整数T，表示测试数据数目。每个测试数据占一行，为正偶数n，2≤n≤800。

输出描述

对每个测试数据，计算P1(n)并输出。

样例输入

2
6
800

样例输出

3
6727090051741041926