Description
Pell数列的定义是这样的：
设 Pi 表示 Pell 数列的第 i 项，则 P1 = 1, P2 = 2, 当 i>2 时，Pi = 2 × Pi-1 + Pi-2 。
Pell 数列的前 10 项如下：
1,2,5,12,29,70,169,408,985,2378,……
现在有 q 次询问，每次询问给你一个整数 n，你需要回答出 Pell 数列的第 n 项 Pn 除以 1000 的余数是多少。
Input
输入的第一行包含一个整数 q（1 ≤ q ≤ 200000）。
接下来 q 行，每行包含一个整数 n（1 ≤ n ≤ 200000），表示一次询问。
Output
输出共 q 行。对于每次询问的 n ，输出一个整数，表示 Pn 除以 1000 的余数。