恭喜你！来到第二关

此关的任务是：从以下给出的序列中找出规律

1 2 3 6 11 20 37 68  125.......

考官有q次询问，每次询问都会给你一个整数x,你需啊快速回答此序列的第x项的值。由于数字过于巨大，你只要回答第x项的值对10003取模的结果即可

第一行：一个整数q,表示询问次数

接下来q行，每行一个整数n,表示要询问第n项的值

1<=q<=10^5

1<=n<=10^5