题目描述

$Frobozz$魔法锁公司专门生产按键式组合门锁。这种门锁由$B$个（$1 \leq B \leq 11$）标号为“$1$”到“$B$”的按键组成。用户需要按下正确的按键组合序列，然后转动门把手即可开锁。如果按键序列正确，门就会神奇地打开。

一个组合是指同时按下$1$个或多个按键。一个序列由一系列组合构成，且至少包含一个组合。在同一个序列中，每个按键只能出现在一个组合中，不能重复使用。此外，序列中不一定要使用所有按键。例如，对于$B = 8$：

                               $(1-2-3)(4)(7-8)$

是一个有效的序列，包含$3$个组合$(1-2-3)$、$(4)$和$(7-8)$。注意，按键$5$和$6$未被使用。

                              $(1-2-3)(2-4)(5-6)$

是无效的序列，因为按键$2$在$(1-2-3)$和$(2-4)$中重复出现。

$Frobozz$公司的$CEO$ $J. Pierpont Flathead$希望您编写一个程序，计算给定$B$值下所有可能的有效序列数量。程序需要处理客户提供的锁订单（数据集），并生成报告，显示订单编号、$B$的值以及可能的有效序列数量。输入数据至少包含一个数据集，但不超过$100$个。

参考资料

$J. Pierpont Flathead$

输入格式

第一行输入一个整数$N$（$1 \leq N \leq 100$），表示数据集的数量。接下来的$N$行，每行包含一个整数$B$，表示门锁的按键数量。

输出格式

对于每个数据集，输出一行，包含数据集编号$B$的值以及有效序列的数量，格式为：数据集编号 B 有效序列数量。

样例输入

3  
3  
4  
3  

样例输出

1 3 25  
2 4 149  
3 3 25  

来源

2006年大纽约地区编程竞赛