說明

菲波那契數列是指這樣的數列：數列的第一個和第二個數都為1，接下來每個數都等於前面2個數之和。 給出一個正整數a，要求菲波那契數列中第a個數對1000取模的結果是多少。

輸入格式

第1行是測試數據的組數n，後面跟著n行輸入。 每組測試數據占1行，包括一個正整數a（1≤a≤1000000）。

輸出格式

n行，每行輸出對應一個輸入。 輸出應是一個正整數，為菲波那契數列中第a個數對1000取模得到的結果。

樣例

4
5
2
19
1

5
1
181
1