题目描述

正整数 $N$ 的一个划分是指若干整数的序列，其和为 $N$，通常用加号连接各数表示。例如：

$15 = 1+2+3+4+5 = 1+2+1+7+1+2+1$

若一个划分从左到右和从右到左读相同，则称为回文划分。例如，第一个划分不是回文的，第二个是。对于包含 $m$ 个整数的回文划分，其左半部分为前 $\lfloor m/2 \rfloor$ 个数，右半部分为后 $\lfloor m/2 \rfloor$ 个数（必须是左半部分的逆序）。

递归回文划分定义为：该划分是回文的，且其左半部分是递归回文的（或为空）。注意，每个整数至少有两个递归回文划分：全1划分和自身单独成一个数的划分。例如，上述第二个例子也是递归回文的。

例如，7的递归回文划分有：
$ 7,\ 1+5+1,\ 2+3+2,\ 1+1+3+1+1,\ 3+1+3,\ 1+1+1+1+1+1+1 $

编写程序，输入整数 $N$，输出其递归回文划分的数量。

输入

第一行包含整数 $N$（$1 \leq N \leq 1000$），表示测试用例数。
每个测试用例占一行，包含一个正整数 $K$（$1 \leq K \leq 1000$），需计算其递归回文划分的数量。

输出

对每个测试用例，输出一行，格式为：
数据集编号 数量
其中数量为 $K$ 的递归回文划分个数。

输入示例 1

3  
4  
7  
20  

输出示例 1

1 4  
2 6  
3 60