UVA12034 比赛名次 Race

$ben,cong$两人赛马，最终名次有$3$种可能：并列第一；$ben$第一$cong$第二；$cong$第一$ben$第二。输入$n(1\leq n\leq1000)$,求$n$人赛马时最终名次的可能性的个数$(mod$ $10056)$

有多组数据。 第一行为一个整数$T(T\leq1000)$,表示数据组数。 接下来的的$T$行，每行一个整数$n$，含义如题。

``Case i: answer`` 其中$answer$为所求的答案$(mod$ $10056)$