张小牛日记

【题目描述】

  1997年2月23日    星期六    晴

   今天天气晴朗，蓝天上飘着朵朵白云。

   今天是星期天，不用上课，不过爸爸叫我先把作业做了。这星期老师教我们认方向，我学会了东南西北，我要好好温习一下。

   老师叫我先找好一个出发点，走N步，每步可以随便选择这四个方向中的一个方向走，每步走的长度都要一样。这是很简单的作业，我很轻松地做了好几次。

   不过好奇怪哦，我有时候能走回出发点，有时候却不能。比如我要走两步，如果我先向东走再向西走，我就可以回到出发点；如果我先向东走再向北走，我就不能回到出发点了。好神奇哦!那么到底我有多少种走法可以走回原地呢?

   我拿着这个问题去问老师，老师说他也不会，好失望哦。不过后来他叫我好好学习，天天向上，长大后就可以出这道题给小朋友做了。

   不过老师会不会骗人啊，到时那些小朋友真的会做吗?

输入格式

   第1行为一个整数T，表示有T组测试数据；

   接下来有T行，每行表示一组测试数据，每组测试数据仅包含一个整数N，表示张小牛一共走了N步。

【输入格式】

第1行为一个整数T，表示有T组测试数据；

接下来有T行，每行表示一组测试数据，每组测试数据仅包含一个整数N，表示张小牛一共走了N步。

【输出格式】

对每组测试数据输出一行，仅含一个整数，表示张小牛有多少种走法能回到出发点。

由于答案可能会很大，你只需输出该数模1997的结果即可(即除以1997后的余数)。

【样例输入】

2
2
10

【样例输出】

4
1597

【提示】

数据范围    ．

   对于20％的数据，保证1≤T≤5，1≤N≤10。

   对于50％的数据，保证1≤T≤20，1≤N≤100。

   对于所有的数据，保证1≤T≤2 000，1≤N≤2 000。

大样例

【来源】

在此键入。