| 问题描述 |
|---|
已知一个数列的第1项为1，第2项为2，从第三项开始起，通项公式是an=2*an-1+an-2，求数列第m项的千位数。 |
| 输入描述 |
多组案例。一个正整数n，表示案例的数量。（n<=100） 每组案例由一个正整数m组成。（m<=10000） |
| 输出描述 |
针对每组案例，输出一个整数，表示数列第m项的千位数。 每组案例输出完要换行。 |
| 样例输入复制样例 |
2 3 10 |
| 样例输出 |
0 2 |
| 相关 |