定义数列 满足 1,& x\in\{1,2,3\};\\a_{x-1}+a_{x-3},& x\geqq4.\end{cases}" 给定 ，请求出 的值。

输入描述:

第一行输入整数 ，表示询问数量。 接下来 行，每行一个整数 。

输出描述:

对于每个询问，在一行上输出 的值（取模 ）。