小镇正在规划一条物资运输专线，道路上依次排布着若干中转站。从第 个中转站出发前往第 号中转站，每一个中转站的通行规则不同。
设走到第 个中转站的合法路线总数为 ，通行规则如下：
到达第 个中转站只有 种路线，即 ；
编号 为偶数的中转站与编号为 的中转站之间有 条路线；
编号 为奇数的中转站与编号为 的中转站有 条路线，与编号为 的中转站有 条路线。
本题有多组测试数据。
第一行一个整数 ,表示测试数据组数。
后 行，每行一个整数 。
行，每行一个整数 ，表示第 个中转站的总合法路线数量。
输入#1：
3 3 5 6
输出#1：
5 35 210
对于 的数据范围， 。
对于 的数据范围， ，。
