题目描述
观测站按日记录潮汐强度序列：第 1 天为 1，第 2 天也为 1，之后每天等于前两天之和；记录仪只显示末三位数字（即对 1000 取模）。
给出天数 $n$，求第 $n$ 天的记录值。多组询问。
输入格式
第一行整数 $T$（询问组数）； 随后 $T$ 行，每行一个整数 $n$。
输出格式
$T$ 行，每行一个整数：第 $n$ 天的记录值（模 1000）。
数据范围
$$1 \le n \le 10^6,\quad T \le 100$$
观测站按日记录潮汐强度序列：第 1 天为 1，第 2 天也为 1，之后每天等于前两天之和；记录仪只显示末三位数字（即对 1000 取模）。
给出天数 $n$，求第 $n$ 天的记录值。多组询问。
第一行整数 $T$（询问组数）； 随后 $T$ 行，每行一个整数 $n$。
$T$ 行，每行一个整数：第 $n$ 天的记录值（模 1000）。
4 1 2 3 10
1 1 2 55
4 5 2 19 1
5 1 181 1