The captain of TITANIC is a mathematics freak. He has recently been given a problem that he is unable to solve. And he has asked your help to solve it.

There are n numbers in a given expression.

X1 X2 X3 ....  Xn

What is the number of ways to put parenthesis in the expression.

For n=4, the different ways are 

(((x1.x2).x3).x4)
((x1.x2).(x3.x4))
(x1.((x2.x3).x4))
(x1.(x2.(x3.x4)))
((x1.(x2.x3)).x4)


Hence the required answer would be 5.

Input
The first line contains the number of test cases t ≤10.
Each of the next t lines contain single integers ≤1000 denoting n.



Output
Display t lines containg the number of ways to put parenthesis in the expression of length n modulo 10000.


Example

Input:
2
4
5


Output:
5
14
#!/usr/bin/python
import sys

catalan=[1 , 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430 , 4862 , 6796 , 8786 , 8012 , 2900 , 4440 , 4845 , 7670 , 4790 , 8700 , 3190 , 420 , 7020 , 3640 , 3650 , 7324 , 1452 , 2152 , 6004 , 360 , 1368 , 2304 , 6909 , 8198 , 3110 , 764 , 1262 , 3492 , 2364 , 1400 , 390 , 8820 , 4020 , 9240 , 700 , 8040 , 3720 , 6320 , 9490 , 1900 , 8572 , 4456 , 6156 , 7512 , 5880 , 9424 , 5972 , 4312 , 2664 , 2080 , 7112 , 8896 , 6336 , 3312 , 125 , 6950 , 5350 , 5100 , 9950 , 8500 , 4700 , 4600 , 6350 , 5700 , 4500 , 7240 , 1020 , 4520 , 40 , 5600 , 2230 , 3940 , 4740 , 4280 , 6100 , 440 , 4520 , 4320 , 4940 , 1000 , 6600 , 800 , 3800 , 5600 , 8000 , 9600 , 4050 , 4300 , 5100 , 1000 , 7340 , 9320 , 7320 , 2640 , 3100 , 7080 , 9240 , 5040 , 9880 , 7600 , 7440 , 1520 , 820 , 2440 , 7000 , 7200 , 8600 , 9600 , 5200 , 6000 , 200 , 3600 , 1600 , 1200 , 2000 , 4624 , 8752 , 4752 , 3629 , 5510 , 7478 , 4684 , 7614 , 8308 , 2860 , 4424 , 2942 , 3172 , 4724 , 3800 , 5180 , 2840 , 1240 , 2880 , 5150 , 4180 , 8740 , 6440 , 6580 , 7800 , 5688 , 7824 , 5724 , 3848 , 7320 , 416 , 6648 , 3408 , 3376 , 4320 , 6118 , 4244 , 2004 , 4568 , 5300 , 8280 , 7640 , 3040 , 980 , 1400 , 5080 , 9440 , 9640 , 480 , 8800 , 9184 , 2332 , 8232 , 1864 , 1360 , 4728 , 9584 , 4064 , 3008 , 4760 , 9264 , 6112 , 1792 , 9664 , 2000 , 1200 , 5600 , 2850 , 6700 , 3500 , 200 , 1100 , 6600 , 6200 , 2000 , 8940 , 120 , 6120 , 8240 , 8600 , 8880 , 2640 , 7440 , 1180 , 6600 , 7640 , 7120 , 920 , 4640 , 6000 , 7600 , 3800 , 6800 , 1600 , 8000 , 5600 , 800 , 4800 , 3600 , 8500 , 2440 , 4120 , 7120 , 7240 , 9600 , 5280 , 3840 , 1640 , 80 , 1600 , 1040 , 320 , 9120 , 1040 , 2000 , 8200 , 1600 , 7600 , 1200 , 6000 , 1200 , 1600 , 9600 , 7200 , 2000 , 9872 , 8256 , 4256 , 4512 , 9280 , 2784 , 2477 , 5142 , 2774 , 3580 , 2622 , 3876 , 8316 , 9272 , 9150 , 1940 , 9220 , 8920 , 8540 , 6200 , 8440 , 9920 , 270 , 5140 , 4900 , 8984 , 8132 , 3832 , 1864 , 3760 , 5388 , 1864 , 9544 , 3168 , 6760 , 3424 , 5792 , 7472 , 5774 , 900 , 8340 , 920 , 9620 , 6440 , 4200 , 8240 , 4820 , 2920 , 4440 , 6400 , 6872 , 5856 , 1056 , 3312 , 8380 , 3224 , 872 , 1712 , 7464 , 4080 , 2112 , 6896 , 5336 , 7312 , 0 , 6000 , 8000 , 8000 , 6000 , 0 , 9750 , 500 , 500 , 1000 , 2500 , 2200 , 600 , 5600 , 3700 , 3000 , 9400 , 3200 , 2200 , 8400 , 8000 , 3200 , 8100 , 4600 , 8200 , 0 , 3000 , 4000 , 4000 , 8000 , 5000 , 8000 , 4000 , 4000 , 8000 , 0 , 9200 , 1600 , 9100 , 8200 , 3000 , 400 , 6200 , 5200 , 4400 , 8000 , 2200 , 7600 , 1600 , 7200 , 0 , 6000 , 8000 , 8000 , 1000 , 0 , 6000 , 8000 , 8000 , 6000 , 0 , 6240 , 7520 , 7520 , 5040 , 7600 , 1280 , 3840 , 640 , 2080 , 4850 , 5740 , 1420 , 3720 , 3740 , 3000 , 7800 , 6400 , 7900 , 9800 , 9000 , 2800 , 5400 , 2400 , 6800 , 8000 , 3180 , 5640 , 9640 , 3280 , 200 , 3760 , 5280 , 8880 , 4360 , 5200 , 8480 , 5840 , 9440 , 480 , 8000 , 2800 , 3900 , 5400 , 9800 , 4000 , 5800 , 4400 , 6400 , 4800 , 3000 , 4640 , 2720 , 6720 , 7440 , 5600 , 8880 , 640 , 6440 , 7680 , 9600 , 5440 , 3520 , 6320 , 9440 , 0 , 8000 , 4000 , 4000 , 8000 , 0 , 8000 , 4000 , 4000 , 500 , 5000 , 8600 , 2800 , 7800 , 5600 , 4000 , 7200 , 6600 , 3600 , 9200 , 4000 , 1600 , 2800 , 4800 , 1600 , 5000 , 4000 , 2000 , 2000 , 4000 , 0 , 4000 , 2000 , 2000 , 4000 , 0 , 5600 , 8800 , 8800 , 7600 , 4000 , 2200 , 1600 , 3600 , 9200 , 4000 , 9600 , 6800 , 8800 , 9600 , 0 , 8000 , 4000 , 4000 , 8000 , 0 , 8000 , 4000 , 4000 , 8000 , 0 , 1840 , 6320 , 6320 , 2640 , 1600 , 6480 , 9440 , 8240 , 9280 , 7600 , 5840 , 4720 , 9645 , 7590 , 1750 , 300 , 5150 , 2900 , 2300 , 9000 , 1550 , 2900 , 4900 , 1800 , 5500 , 4280 , 8440 , 7440 , 7630 , 1700 , 5460 , 7880 , 980 , 5560 , 4200 , 2080 , 2140 , 5240 , 9080 , 8000 , 9800 , 2400 , 6400 , 6800 , 2750 , 5300 , 2900 , 7400 , 9300 , 3000 , 9640 , 2720 , 9220 , 2440 , 600 , 880 , 1640 , 7440 , 9680 , 9600 , 4940 , 4520 , 7320 , 1440 , 5000 , 6000 , 8000 , 8000 , 1000 , 0 , 6000 , 8000 , 8000 , 6000 , 0 , 1200 , 6350 , 100 , 7700 , 3000 , 4900 , 2200 , 6200 , 6400 , 500 , 2200 , 2600 , 1600 , 2200 , 0 , 8000 , 4000 , 6500 , 3000 , 5000 , 8000 , 9000 , 4000 , 8000 , 0 , 2200 , 5600 , 5600 , 1200 , 8000 , 6400 , 9200 , 3200 , 7900 , 3000 , 200 , 1600 , 600 , 5200 , 0 , 6000 , 3000 , 8000 , 6000 , 0 , 6000 , 8000 , 8000 , 6000 , 5000 , 8624 , 2752 , 2752 , 5504 , 3760 , 4528 , 3584 , 1264 , 6608 , 5360 , 6224 , 592 , 7072 , 5024 , 800 , 6630 , 7940 , 2340 , 1080 , 4900 , 7880 , 2840 , 1040 , 3780 , 9800 , 1848 , 3504 , 4904 , 8208 , 8720 , 5136 , 4308 , 3768 , 296 , 6720 , 2728 , 4624 , 5584 , 928 , 7800 , 3280 , 2640 , 3040 , 8480 , 6400 , 6080 , 7440 , 5140 , 1480 , 3800 , 9344 , 9512 , 2912 , 6224 , 9760 , 2248 , 2144 , 7824 , 7728 , 2160 , 1424 , 5392 , 4272 , 8824 , 4000 , 400 , 5200 , 7200 , 6400 , 2000 , 8400 , 1200 , 7200 , 400 , 4000 , 9280 , 7440 , 9440 , 880 , 700 , 1560 , 6680 , 9280 , 9160 , 9200 , 9680 , 9440 , 40 , 3680 , 2000 , 5200 , 7600 , 3600 , 3200 , 6000 , 6200 , 1600 , 9600 , 7200 , 2000 , 480 , 7040 , 3040 , 2080 , 3200 , 3760 , 7280 , 4880 , 5360 , 7200 , 7680 , 440 , 5040 , 7680 , 4000 , 8400 , 9200 , 1200 , 4400 , 2000 , 4400 , 9200 , 5200 , 6400 , 4000 , 6288 , 3424 , 5424 , 2848 , 3120 , 4336 , 5008 , 1168 , 5296 , 6320 , 5888 , 2704 , 6464 , 9488 , 5600 , 6160 , 6080 , 6880 , 9810 , 4300 , 1660 , 1880 , 6780 , 7960 , 8600 , 8256 , 1388 , 3688 , 1176 , 7840 , 3992 , 1776 , 2896 , 4512 , 9340 , 7416 , 7928 , 6048 , 3816 , 3600 , 5360 , 9680 , 9480 , 7760 , 6800 , 6960 , 1280 , 3680 , 1760 , 5600 , 4908 , 8584 , 9384 , 3568 , 9320 , 1136 , 8208 , 5968 , 9496 , 5120 , 4368 , 8944 , 1104 , 9168 , 4000 , 2400 , 6200 , 3200 , 8400 , 2000 , 400 , 7200 , 3200 , 2400 , 4000 , 2880 , 240 , 2240 , 6480 , 7200 , 7760 , 5280 , 2380 , 2360 , 8200 , 5280 , 9240 , 1840 , 9280 , 2000 , 200 , 7600 , 3600 , 3200 , 6000 , 1200 , 1600 , 9600 , 2200 , 2000 , 8880 , 240 , 6240 , 8480 , 9200 , 8560 , 1680 , 7280 , 8160 , 3200 , 6080 , 2640 , 240 , 6080 , 9000 , 6400 , 3200 , 5200 , 2400 , 2000 , 2400 , 3200 , 9200 , 4400 , 4000 , 6784 , 2432 , 4432 , 864 , 8160 , 8448 , 7344 , 4224 , 7728 , 7760 , 784 , 5072 , 4752 , 9584 , 8800 , 3680 , 5840 , 4240 , 8880 , 6400 , 1680 , 8740 , 6440 , 9080 , 2800 , 9048 , 1104 , 1504 , 5408 , 3720 , 336 , 1408 , 8368 , 4496 , 4720 , 7728 , 6624 , 6584 , 6928 , 4800 , 480 , 6240 , 2640 , 3680 , 2400 , 3280 , 7040 , 240 , 9680 , 800 , 1984 , 7232 , 1632 , 4664 , 1360 , 528 , 7984 , 2464 , 9808 , 1760 , 9264 , 4112 , 5792 , 3664 , 0 , 6000 , 8000 , 8000 , 6000 , 0 , 6000 , 8000 , 8000 , 6000 , 0 , 5200 , 9600 , 9600 , 9200 , 8000 , 400 , 1200 , 5200 , 4400 , 8000 , 6200 , 9600 , 3600 , 1200 , 0 , 8000 , 4000 , 4000 , 8000 , 0 , 8000 , 4000 , 4000 , 8000 , 0 , 7200 , 5600 , 5600 , 1200 , 8000 , 6400 , 9200 , 3200 , 400 , 8000 , 5200 , 1600 , 5600 , 5200 , 0 , 6000 , 8000 , 8000 , 6000 , 0 , 6000 , 8000 , 8000 , 6000 , 0 , 5440]




cases=input()
for i in xrange(cases):
	n=input()
	print catalan[n-1]