Problem : 53 - 買醬油II

Problem Statistics

Solved Member: 50　　Submission: 208　　User Tried: 55

Statement:

梓喵又回來買醬油了！！

自從上一次，梓喵去買醬油了之後，你已經被她的腳踏車撞到而得到幸福了。(如果你已經AC過這題的話...)

這一次，梓喵又選擇了不一樣的路線來走，紳士的你又想要再去被她撞一次了，於是根據你尾隨她N-1天記錄下的結果之後，你又發現了神秘的規律：

１.梓喵住在城鎮的左上角(0,0)。
２.梓喵住的城鎮是一個邊長為L(1<=L<=10000)的正方形，城鎮的街道為棋盤狀，任一條直的街道和橫的街道形成一個十字路口。
３.梓喵很喜歡運動，所以會騎車到城鎮最角落的便利商店(L,L)買醬油。
４.梓喵很喜歡運動但是為了追求快感(路線比較快的意思)，所以她只會走最短路徑，也就是她只會往東或是往南騎去。
５.由於梓喵聽說城鎮的左下角有很多怪怪的東西，所以她不想要跨越中間的線(y=x)，但是可以踩到線上面，也就是說可以到路口(X,X)，但不能到(X,X+1)。

我們可以用下面的圖來簡略表示，右邊為東，下面為南：

現在你知道了城鎮的大小，你想快速的知道她今天可能有幾種路線可以走呢？

Input:Output:

第一行有一個整數N，表示測資數量。(1<=N<=1000)
接下來有N筆測資。
每筆測資有一個整數L，代表城鎮的大小。(1<=L<=10000)

對於每一筆測資，輸出梓喵今天可能走的路線數，為了避免數字太大，將結果Mod 910193輸出就可以了。

Sample Input:Sample Output:

3
1
2
3

1
2
5

HINT:

當L=3時，圖形如下：

Problem Setter

ツンデレkevinpttさん

Testdata:

Test	Time	Memory	Score
0	1500ms	32768kb
1	1500ms	32768kb	20
2	1500ms	32768kb	20
3	1500ms	32768kb	20
4	1500ms	32768kb	20
5	1500ms	32768kb	20