#include <cstdio>
int n,T;
int ans[5001]={0,
1,
2,
2,
2,
4,
5,
4,
8,
8,
7,
11,
8,
13,
4,
11,
12,
8,
12,
2,
13,
7,
22,
2,
8,
13,
26,
4,
26,
29,
17,
27,
26,
7,
33,
20,
16,
22,
29,
4,
13,
22,
25,
14,
22,
37,
18,
46,
42,
46,
9,
41,
12,
7,
26,
42,
24,
5,
44,
53,
52,
58,
29,
22,
12,
48,
27,
30,
58,
52,
49,
57,
13,
14,
32,
24,
75,
8,
67,
56,
40,
61,
51,
77,
35,
57,
74,
63,
75,
12,
72,
89,
11,
32,
32,
59,
61,
62,
89,
22,
31,
67,
33,
101,
101,
34,
74,
90,
89,
61,
73,
18,
26,
72,
96,
25,
53,
93,
42,
11,
80,
42,
94,
32,
80,
12,
7,
97,
22,
82,
119,
94,
88,
60,
123,
88,
119,
76,
128,
34,
116,
57,
140,
103,
133,
107,
44,
100,
53,
20,
51,
12,
74,
59,
146,
111,
13,
119,
39,
9,
142,
31,
154,
99,
26,
5,
99,
110,
135,
155,
99,
86,
2,
8,
49,
16,
126,
149,
76,
123,
101,
168,
128,
94,
51,
38,
107,
119,
70,
64,
149,
4,
62,
94,
99,
61,
2,
39,
164,
149,
73,
109,
83,
81,
169,
26,
181,
166,
109,
140,
89,
64,
62,
94,
30,
168,
27,
31,
192,
82,
215,
7,
184,
199,
158,
198,
215,
62,
157,
58,
18,
51,
200,
57,
226,
2,
236,
50,
106,
188,
22,
128,
149,
162,
206,
228,
150,
26,
205,
18,
9,
107,
68,
188,
165,
184,
238,
48,
95,
92,
62,
143,
164,
238,
156,
64,
86,
134,
130,
245,
258,
252,
62,
191,
138,
71,
243,
102,
111,
187,
25,
95,
59,
186,
185,
274,
111,
261,
72,
272,
42,
137,
235,
62,
86,
144,
193,
77,
146,
265,
156,
54,
188,
40,
49,
125,
110,
16,
29,
218,
219,
68,
138,
268,
70,
223,
296,
142,
146,
247,
49,
133,
310,
131,
63,
60,
94,
315,
59,
240,
177,
14,
226,
332,
164,
94,
53,
227,
33,
130,
331,
97,
23,
316,
114,
271,
67,
339,
330,
247,
299,
189,
278,
158,
283,
54,
215,
49,
219,
157,
31,
344,
128,
37,
213,
335,
57,
298,
102,
9,
356,
99,
362,
342,
133,
14,
121,
30,
64,
314,
102,
318,
209,
41,
34,
57,
247,
77,
219,
96,
248,
177,
238,
169,
268,
342,
347,
256,
31,
278,
118,
369,
33,
395,
229,
16,
218,
158,
208,
250,
9,
335,
75,
93,
146,
399,
230,
116,
357,
372,
282,
257,
193,
152,
269,
131,
233,
258,
7,
376,
170,
222,
244,
242,
393,
407,
154,
47,
286,
191,
422,
340,
217,
83,
209,
233,
374,
355,
144,
87,
266,
238,
44,
363,
197,
240,
377,
297,
167,
453,
282,
279,
387,
358,
254,
107,
414,
427,
117,
220,
342,
333,
177,
199,
396,
280,
113,
22,
348,
14,
424,
162,
86,
339,
219,
141,
408,
432,
117,
108,
400,
436,
236,
195,
145,
456,
295,
371,
122,
69,
360,
312,
197,
108,
326,
396,
259,
161,
197,
20,
385,
369,
225,
161,
8,
182,
358,
215,
224,
167,
124,
42,
225,
263,
96,
100,
26,
129,
330,
524,
214,
247,
187,
31,
380,
334,
183,
251,
254,
366,
336,
56,
482,
491,
206,
278,
39,
162,
107,
14,
441,
13,
189,
330,
297,
238,
104,
298,
552,
491,
456,
480,
310,
396,
73,
205,
59,
177,
208,
75,
447,
520,
394,
402,
332,
507,
157,
268,
196,
388,
249,
179,
498,
493,
471,
577,
501,
85,
316,
580,
508,
502,
458,
488,
241,
316,
363,
395,
259,
589,
113,
255,
256,
364,
240,
288,
27,
304,
172,
182,
73,
319,
126,
152,
172,
379,
170,
420,
110,
151,
156,
199,
217,
258,
560,
383,
132,
379,
290,
537,
76,
360,
281,
329,
389,
568,
425,
440,
487,
553,
466,
531,
318,
619,
541,
23,
25,
246,
27,
205,
157,
226,
212,
445,
193,
420,
338,
249,
457,
250,
439,
594,
12,
285,
256,
298,
68,
265,
290,
287,
391,
47,
443,
524,
650,
193,
104,
202,
344,
234,
449,
639,
385,
98,
519,
237,
591,
228,
305,
457,
441,
518,
631,
73,
112,
346,
74,
298,
500,
539,
673,
588,
670,
248,
316,
262,
513,
705,
405,
140,
229,
260,
339,
639,
477,
637,
706,
125,
218,
609,
196,
600,
89,
285,
377,
472,
508,
697,
485,
24,
142,
535,
421,
76,
176,
320,
358,
597,
641,
643,
590,
320,
407,
554,
518,
250,
194,
459,
434,
110,
660,
203,
475,
530,
719,
313,
686,
275,
411,
735,
727,
285,
146,
572,
627,
160,
369,
82,
398,
320,
169,
421,
508,
187,
123,
356,
384,
747,
64,
449,
101,
26,
118,
228,
410,
684,
540,
179,
299,
726,
16,
385,
44,
737,
97,
391,
344,
88,
740,
197,
436,
713,
114,
433,
308,
38,
140,
377,
785,
223,
65,
422,
505,
192,
333,
771,
645,
169,
263,
679,
245,
389,
396,
823,
64,
458,
671,
117,
57,
795,
16,
477,
422,
96,
75,
343,
501,
418,
359,
230,
552,
274,
590,
77,
392,
773,
650,
464,
419,
783,
159,
20,
584,
223,
424,
843,
111,
708,
590,
127,
483,
793,
164,
628,
510,
479,
408,
633,
159,
635,
708,
173,
553,
125,
162,
76,
841,
369,
716,
324,
529,
638,
852,
445,
669,
31,
481,
243,
814,
752,
90,
632,
813,
209,
546,
662,
196,
810,
894,
761,
700,
219,
629,
892,
535,
779,
714,
706,
806,
272,
578,
157,
233,
866,
297,
786,
123,
576,
793,
312,
396,
57,
264,
223,
829,
639,
219,
508,
853,
527,
560,
116,
501,
866,
200,
933,
292,
573,
867,
575,
885,
454,
607,
199,
329,
69,
428,
199,
229,
892,
257,
611,
770,
636,
787,
213,
635,
420,
790,
479,
134,
164,
386,
145,
475,
33,
882,
585,
107,
428,
867,
766,
669,
540,
967,
559,
855,
526,
696,
973,
592,
184,
635,
321,
262,
237,
474,
60,
715,
183,
35,
678,
261,
941,
244,
131,
192,
656,
335,
609,
154,
669,
947,
635,
952,
589,
79,
825,
891,
569,
63,
685,
918,
850,
64,
377,
58,
526,
75,
268,
754,
535,
925,
696,
116,
879,
999,
708,
1019,
880,
984,
71,
923,
810,
394,
127,
450,
198,
409,
835,
348,
143,
524,
194,
178,
54,
545,
274,
840,
608,
604,
14,
819,
417,
787,
509,
965,
322,
1013,
661,
310,
867,
983,
900,
194,
815,
238,
1061,
262,
1063,
714,
316,
613,
559,
725,
239,
899,
447,
87,
151,
862,
902,
327,
110,
612,
118,
212,
123,
626,
407,
816,
832,
994,
705,
59,
943,
529,
193,
437,
1068,
660,
410,
982,
377,
838,
728,
1017,
738,
375,
1023,
489,
81,
758,
433,
774,
938,
936,
734,
281,
1036,
567,
1010,
477,
194,
830,
309,
939,
902,
984,
1059,
619,
212,
591,
480,
818,
483,
951,
811,
129,
212,
170,
307,
1020,
781,
112,
958,
62,
125,
402,
181,
676,
726,
1149,
718,
222,
1091,
506,
329,
988,
634,
843,
639,
436,
1133,
509,
295,
921,
668,
89,
1023,
376,
96,
829,
471,
966,
1136,
238,
1135,
283,
184,
1124,
870,
997,
1024,
479,
1109,
970,
841,
1009,
62,
387,
264,
875,
668,
118,
789,
320,
46,
765,
891,
692,
819,
614,
295,
1004,
520,
1013,
914,
473,
280,
610,
775,
1148,
982,
680,
478,
1017,
1141,
269,
1093,
686,
550,
1000,
672,
50,
133,
871,
538,
82,
117,
365,
466,
984,
712,
127,
517,
490,
482,
112,
798,
634,
342,
504,
778,
184,
1153,
656,
567,
748,
1157,
451,
546,
1168,
1224,
1252,
104,
836,
566,
321,
185,
322,
184,
282,
2,
681,
263,
836,
956,
389,
63,
1062,
1195,
176,
65,
797,
737,
195,
360,
678,
394,
1202,
843,
932,
747,
906,
11,
786,
586,
41,
1214,
244,
209,
1132,
872,
742,
785,
1209,
961,
481,
183,
1187,
889,
63,
1235,
1112,
680,
364,
359,
1073,
1027,
530,
236,
76,
82,
580,
135,
1057,
776,
424,
835,
960,
994,
860,
574,
341,
1307,
743,
730,
151,
82,
298,
1133,
46,
1239,
1310,
909,
420,
607,
1200,
798,
525,
578,
1316,
1127,
63,
221,
342,
1269,
863,
697,
358,
243,
1079,
911,
688,
545,
1300,
1152,
952,
931,
131,
1253,
544,
764,
1324,
35,
1199,
977,
414,
696,
131,
83,
784,
1171,
35,
175,
927,
759,
590,
1005,
1046,
283,
1013,
1044,
824,
424,
1182,
1247,
514,
469,
148,
374,
976,
1120,
801,
531,
211,
221,
1105,
922,
248,
464,
1353,
176,
587,
886,
361,
257,
31,
71,
852,
685,
358,
426,
1335,
124,
677,
690,
234,
419,
31,
1311,
515,
788,
319,
389,
1414,
103,
669,
1300,
545,
330,
162,
82,
886,
499,
596,
372,
206,
470,
486,
1154,
868,
862,
610,
145,
1192,
1356,
862,
799,
370,
701,
1262,
61,
166,
1253,
746,
1202,
218,
46,
1199,
1387,
915,
1050,
254,
527,
223,
246,
179,
5,
692,
492,
215,
458,
251,
601,
1287,
816,
997,
1077,
613,
713,
1158,
1256,
1100,
963,
873,
1473,
162,
549,
239,
510,
1450,
150,
884,
775,
902,
434,
639,
813,
766,
1343,
1154,
1413,
1065,
963,
252,
532,
354,
418,
34,
489,
944,
1075,
956,
995,
854,
1055,
399,
63,
1453,
1511,
1292,
1369,
512,
1052,
494,
560,
650,
803,
173,
1286,
1491,
1413,
965,
4,
486,
802,
982,
655,
544,
320,
1514,
1522,
1413,
1374,
1354,
1438,
216,
777,
915,
608,
311,
865,
58,
241,
1291,
266,
1500,
303,
730,
1005,
947,
1318,
1007,
730,
69,
573,
1388,
348,
1364,
47,
1096,
1253,
1402,
159,
1050,
1216,
865,
578,
818,
669,
777,
572,
1412,
723,
1565,
356,
200,
82,
1017,
1432,
1458,
962,
975,
1544,
786,
1089,
930,
790,
587,
602,
295,
550,
82,
303,
219,
853,
1472,
279,
145,
56,
1324,
386,
1173,
1205,
1080,
1367,
942,
1543,
158,
947,
651,
1071,
1095,
919,
712,
720,
620,
455,
467,
772,
8,
728,
809,
756,
283,
576,
110,
1489,
1257,
188,
230,
296,
1151,
371,
92,
1569,
250,
267,
1311,
115,
1406,
67,
1410,
380,
951,
1292,
1319,
1478,
1511,
1611,
1140,
134,
1297,
1377,
1186,
150,
754,
1526,
1144,
19,
1237,
174,
1160,
1067,
988,
1508,
1170,
705,
202,
1449,
1161,
50,
133,
128,
1155,
1635,
1111,
1534,
1476,
400,
1213,
88,
1659,
348,
1670,
221,
1472,
1614,
1445,
353,
236,
449,
1630,
186,
38,
372,
483,
507,
1688,
214,
506,
705,
505,
838,
289,
506,
534,
974,
1179,
825,
130,
785,
782,
769,
1070,
1709,
756,
1385,
1473,
1590,
1527,
1686,
1459,
1379,
1734,
291,
1673,
945,
1250,
538,
498,
574,
851,
825,
459,
934,
852,
1143,
312,
1434,
685,
1240,
1093,
1363,
1418,
215,
1517,
375,
34,
217,
398,
549,
1715,
523,
735,
615,
943,
1299,
740,
1336,
1117,
1205,
1060,
142,
1193,
1563,
111,
736,
471,
376,
1691,
560,
164,
537,
676,
1459,
758,
1289,
1733,
1755,
1448,
217,
1729,
1779,
284,
677,
732,
1672,
514,
1231,
895,
1455,
1448,
1530,
1399,
198,
334,
295,
116,
1114,
625,
839,
1103,
1642,
1107,
141,
7,
204,
8,
186,
244,
803,
103,
705,
801,
1075,
1254,
1583,
1371,
1804,
49,
712,
173,
1278,
633,
1353,
711,
1612,
37,
1714,
1462,
297,
101,
394,
938,
1255,
775,
1662,
1672,
288,
1683,
832,
317,
315,
645,
921,
1172,
121,
1153,
1696,
280,
436,
587,
943,
478,
1168,
1088,
93,
1383,
427,
1777,
330,
1080,
1251,
1098,
240,
1591,
368,
1591,
48,
505,
1006,
481,
1556,
1374,
52,
154,
831,
134,
835,
768,
1245,
1367,
636,
356,
1865,
424,
933,
1085,
1503,
1214,
1867,
1450,
267,
542,
1196,
598,
1748,
1559,
1835,
1744,
845,
388,
516,
1163,
1219,
1855,
806,
1713,
556,
1116,
1285,
1355,
1806,
1526,
206,
533,
844,
917,
114,
1523,
68,
32,
690,
1175,
1898,
1332,
1320,
1884,
443,
732,
1137,
621,
1748,
20,
381,
859,
1206,
997,
1135,
1403,
332,
361,
1210,
790,
1199,
1476,
158,
127,
733,
173,
1480,
1108,
1635,
1934,
529,
67,
1179,
1441,
34,
115,
1014,
831,
1190,
729,
1568,
50,
1215,
1889,
745,
1441,
109,
315,
829,
295,
1443,
1230,
114,
1359,
1017,
487,
1416,
1585,
138,
396,
896,
852,
1133,
1444,
251,
520,
1167,
527,
1791,
1613,
601,
211,
871,
947,
1570,
17,
998,
618,
1774,
1271,
33,
76,
784,
775,
1511,
1295,
1995,
433,
576,
1092,
1761,
1322,
882,
924,
1944,
1325,
439,
1907,
787,
597,
1193,
1687,
1477,
41,
1322,
1473,
303,
205,
891,
499,
1853,
1547,
427,
96,
1516,
1297,
495,
348,
945,
1021,
79,
95,
244,
1172,
1241,
1496,
593,
243,
890,
1460,
1650,
1957,
809,
956,
1616,
1723,
825,
687,
1874,
1365,
1846,
367,
1104,
1499,
1800,
119,
675,
735,
1826,
1756,
718,
149,
167,
1594,
578,
652,
1362,
1604,
2043,
1992,
1047,
1542,
636,
1131,
1076,
1471,
73,
1925,
1031,
753,
1590,
1696,
293,
649,
1950,
1760,
549,
821,
1219,
1362,
597,
651,
912,
1317,
1936,
601,
1440,
1075,
1713,
392,
939,
1144,
228,
2072,
542,
1190,
1817,
230,
1643,
972,
2,
1967,
870,
1719,
1954,
1369,
893,
1141,
1338,
2096,
1074,
638,
72,
117,
955,
1392,
22,
199,
546,
920,
163,
128,
1548,
189,
1758,
557,
1095,
1287,
2133,
1869,
970,
1347,
2137,
295,
1424,
865,
345,
822,
1005,
1867,
390,
260,
1194,
1477,
308,
311,
1966,
973,
360,
1076,
1591,
207,
1183,
647,
1244,
1919,
410,
819,
256,
1898,
1074,
1402,
7,
656,
1292,
938,
2060,
130,
1014,
1691,
587,
894,
1681,
4,
732,
1105,
2180,
2024,
769,
1070,
1884,
345,
1988,
1012,
4,
381,
1898,
7,
407,
936,
1676,
1709,
761,
977,
643,
2106,
827,
1799,
798,
757,
2054,
1800,
265,
1287,
1916,
240,
1350,
470,
433,
514,
1261,
2070,
450,
463,
1456,
155,
935,
1066,
1108,
547,
1444,
1907,
427,
735,
1472,
1616,
746,
1416,
148,
270,
1952,
1346,
699,
767,
2105,
2221,
1628,
1249,
1630,
541,
1199,
1842,
1101,
360,
1716,
237,
1560,
2132,
371,
402,
1985,
1924,
193,
1017,
379,
8,
1403,
152,
1131,
1135,
2274,
83,
714,
1426,
555,
1037,
2024,
1180,
849,
1438,
43,
1212,
1890,
1954,
1000,
1298,
2147,
817,
2101,
1737,
515,
1201,
111,
364,
1568,
1654,
655,
1224,
1704,
365,
1684,
1750,
1409,
831,
2147,
486,
1692,
1687,
2216,
952,
1701,
201,
33,
534,
620,
1216,
24,
931,
1399,
1072,
1141,
1115,
1662,
331,
2192,
2115,
744,
1231,
143,
981,
1800,
258,
195,
1818,
180,
794,
2025,
2013,
1388,
1571,
262,
1436,
1986,
1758,
636,
1752,
402,
1073,
483,
2280,
656,
1550,
522,
1465,
2345,
269,
1886,
1909,
998,
1157,
1098,
518,
2017,
606,
1306,
2134,
955,
778,
2124,
710,
1720,
2195,
1763,
287,
41,
1273,
47,
773,
1323,
1555,
909,
1262,
13,
614,
2343,
1908,
1263,
1903,
1224,
972,
543,
689,
1255,
2268,
935,
1808,
885,
952,
2279,
336,
1732,
523,
1067,
1027,
442,
777,
1909,
330,
2225,
1896,
1091,
1744,
767,
1387,
2304,
213,
1552,
2101,
554,
2403,
722,
978,
2442,
444,
1715,
2248,
1658,
1524,
266,
1157,
196,
750,
132,
1825,
921,
1986,
994,
1872,
2413,
799,
2372,
516,
1876,
2096,
1637,
1387,
290,
1301,
73,
810,
211,
2352,
1274,
2171,
864,
1601,
419,
481,
71,
444,
1800,
2359,
1362,
1676,
670,
1738,
471,
793,
142,
2235,
1781,
654,
1457,
2313,
525,
1473,
357,
586,
1915,
491,
1896,
2175,
1459,
2287,
1161,
1436,
1179,
975,
2352,
567,
1714,
156,
474,
1103,
552,
2141,
699,
1698,
546,
522,
1987,
2328,
1473,
2379,
2231,
1720,
1013,
2111,
1085,
1331,
695,
1024,
1987,
2404,
1502,
355,
2139,
1510,
1205,
1802,
574,
1552,
323,
1327,
2461,
776,
1947,
173,
2371,
2434,
1017,
2044,
494,
1888,
2376,
85,
2284,
781,
1797,
578,
2493,
1840,
1809,
2109,
574,
2100,
734,
1920,
2174,
1202,
2414,
845,
213,
1886,
2089,
642,
1565,
534,
889,
1744,
940,
1398,
2354,
880,
695,
537,
2139,
1256,
2207,
974,
17,
60,
1290,
1841,
1443,
282,
1147,
787,
332,
2066,
318,
1154,
586,
194,
1541,
603,
2575,
132,
2055,
2436,
970,
2520,
1434,
2310,
1155,
914,
583,
1221,
2519,
1320,
2609,
104,
70,
661,
2584,
394,
60,
2537,
1305,
100,
1174,
102,
2119,
1597,
1441,
1758,
807,
2215,
931,
567,
671,
1530,
2520,
1332,
573,
2642,
2508,
931,
2394,
349,
2455,
529,
1648,
457,
1895,
2455,
1810,
1494,
987,
2289,
1271,
141,
1448,
2055,
541,
1749,
825,
1436,
656,
1196,
256,
833,
211,
1337,
1954,
356,
2086,
269,
2257,
652,
2598,
2345,
2432,
810,
1885,
2664,
2532,
298,
996,
2101,
1410,
2326,
2365,
1602,
1352,
2545,
1247,
2597,
1168,
1590,
1032,
2259,
1178,
1488,
1284,
1137,
706,
1852,
964,
1801,
1335,
1673,
294,
1597,
308,
1521,
296,
522,
49,
1569,
302,
845,
202,
1082,
2664,
642,
2730,
1349,
1344,
756,
2288,
882,
424,
855,
2547,
446,
2473,
2712,
1773,
727,
189,
62,
50,
1016,
2734,
413,
2748,
1178,
1869,
391,
2317,
1286,
205,
17,
2753,
1162,
2289,
1295,
2730,
2731,
2340,
812,
1958,
1012,
2675,
2683,
2645,
965,
2375,
1284,
177,
1012,
2508,
766,
2608,
675,
158,
274,
434,
1258,
2605,
1551,
130,
1370,
2251,
834,
709,
728,
718,
1230,
239,
1716,
241,
2064,
914,
1323,
476,
1316,
569,
2540,
1153,
559,
1082,
2033,
766,
1930,
1608,
1975,
876,
1741,
1173,
2783,
2238,
1391,
1258,
148,
2107,
407,
2462,
2142,
1765,
297,
2029,
161,
2065,
385,
2233,
1224,
490,
1562,
724,
959,
2142,
772,
2682,
1370,
708,
1220,
770,
1626,
746,
1941,
1114,
1515,
782,
2617,
1250,
2454,
2371,
2068,
1468,
2722,
1562,
236,
2511,
2669,
2313,
768,
1672,
661,
414,
141,
220,
1094,
70,
1040,
783,
1576,
654,
1779,
892,
2716,
2614,
1977,
1138,
2669,
2274,
658,
1668,
62,
2183,
623,
2542,
16,
605,
480,
513,
1299,
925,
2550,
1392,
1759,
640,
2511,
1558,
2751,
1957,
1409,
2336,
635,
2693,
762,
100,
721,
593,
1622,
143,
1303,
987,
1724,
547,
2877,
979,
302,
1215,
1994,
1693,
299,
1866,
201,
2504,
382,
2889,
1238,
764,
1739,
1683,
1758,
763,
2127,
1324,
2832,
624,
1760,
2037,
714,
336,
1523,
234,
169,
453,
1493,
1166,
1377,
2548,
2612,
1747,
2946,
2168,
2862,
2648,
539,
2497,
1432,
2857,
2040,
923,
1767,
1161,
2275,
1529,
61,
1707,
2947,
2474,
1233,
2264,
1400,
1049,
1433,
856,
1871,
638,
129,
1500,
2106,
1744,
405,
1986,
1096,
373,
1000,
1064,
1231,
1347,
2572,
2237,
2231,
1232,
178,
2493,
1148,
511,
2915,
529,
2867,
1305,
2794,
1240,
2822,
2696,
2829,
2319,
499,
621,
1525,
726,
2694,
1255,
2433,
2427,
113,
2384,
636,
2785,
1291,
3011,
485,
736,
2124,
1036,
292,
2580,
3019,
2536,
768,
2917,
1230,
1417,
1984,
758,
2676,
2065,
2994,
2453,
299,
2579,
1071,
530,
2477,
1690,
1759,
2639,
2921,
2460,
889,
532,
1245,
272,
1503,
980,
2653,
2769,
2258,
2404,
880,
556,
1855,
661,
1756,
1478,
2646,
2030,
562,
509,
1083,
326,
2115,
1482,
1972,
2546,
2904,
1610,
602,
2865,
1344,
444,
1086,
1447,
2339,
1790,
1287,
2877,
862,
26,
1557,
660,
2398,
2526,
2929,
2673,
916,
96,
2073,
910,
1801,
1184,
2644,
1728,
889,
109,
1329,
740,
1892,
1571,
324,
2871,
326,
2091,
1386,
722,
1986,
2221,
2154,
1704,
559,
3082,
2251,
468,
1823,
1581,
2606,
2327,
110,
865,
913,
3021,
2629,
2213,
3084,
2704,
3118,
2276,
1377,
673,
2543,
1486,
1989,
2466,
382,
657,
2024,
1472,
1447,
1439,
2912,
2178,
1253,
1214,
2133,
591,
2967,
2558,
76,
2274,
310,
226,
1551,
1028,
151,
2893,
739,
2855,
1528,
725,
1859,
1862,
2570,
2046,
1105,
2374,
1515,
2704,
1812,
1651,
752,
3008,
2648,
614,
1610,
1470,
3010,
1642,
350,
606,
1170,
889,
546,
2826,
966,
319,
2208,
751,
2835,
2270,
350,
3102,
336,
959,
1397,
1190,
34,
2191,
411,
77,
1847,
1250,
3113,
2192,
387,
2777,
1645,
689,
2669,
979,
2751,
2638,
1129,
344,
2475,
2115,
2300,
2759,
2169,
2876,
2490,
2079,
3080,
2110,
813,
3136,
1667,
2005,
1909,
2079,
962,
313,
2727,
1314,
2821,
2640,
375,
2545,
1005,
1739,
2902,
2549,
1544,
358,
2063,
1320,
155,
1445,
41,
286,
2004,
1870,
2496,
2465,
466,
13,
2065,
1759,
2022,
2115,
1049,
3070,
2096,
1514,
2604,
1905,
883,
529,
2159,
1195,
2606,
2143,
1014,
3104,
2285,
2225,
2363,
377,
1579,
407,
2220,
2099,
2995,
2179,
1219,
268,
2851,
3205,
2426,
3134,
1927,
1374,
182,
2424,
543,
334,
1236,
1218,
2732,
3181,
797,
644,
2902,
1676,
3214,
314,
1414,
3295,
2589,
2003,
654,
125,
927,
1281,
3104,
1968,
1297,
854,
1910,
958,
3205,
2987,
910,
1099,
2044,
1548,
752,
37,
2730,
1597,
2437,
2611,
452,
302,
2536,
2289,
3093,
3337,
2061,
1358,
22,
3112,
739,
2838,
1611,
1858,
755,
1001,
3274,
695,
3180,
2522,
1125,
850,
1677,
1253,
3293,
2779,
1557,
1444,
2165,
1980,
921,
270,
1496,
1712,
408,
2070,
1666,
375,
2692,
123,
3218,
679,
2124,
1337,
49,
3273,
1241,
310,
2744,
2525,
661,
1852,
2134,
1793,
997,
3355,
3011,
739,
2371,
2307,
1152,
3324,
2632,
3018,
535,
416,
2495,
1956,
63,
461,
1918,
400,
3078,
3045,
663,
1814,
2077,
2053,
824,
255,
2826,
1542,
3236,
133,
1564,
805,
2925,
2603,
943,
64,
230,
2331,
632,
749,
2387,
2014,
52,
2953,
1456,
2550,
2565,
3252,
1900,
86,
3193,
2830,
1021,
160,
2384,
2867,
50,
1125,
2326,
1496,
699,
3246,
2241,
1906,
117,
2803,
1418,
622,
179,
3139,
722,
1387,
2766,
2611,
422,
1226,
2665,
1560,
335,
493,
2264,
3072,
3208,
17,
1997,
1777,
658,
299,
1098,
1557,
3315,
2660,
1628,
2309,
2427,
3196,
1966,
1745,
3177,
2812,
1776,
3335,
2683,
1943,
2086,
1510,
2109,
2772,
1257,
536,
3093,
2332,
552,
3188,
2995,
2397,
1077,
1908,
2445,
1898,
1091,
50,
2596,
1984,
3270,
149,
2057,
1786,
359,
1025,
1938,
1788,
660,
3376,
2355,
1998,
441,
2816,
2192,
2276,
272,
1213,
1202,
1136,
605,
3327,
3322,
2125,
3475,
3273,
2234,
1046,
266,
1030,
577,
1290,
980,
1001,
2819,
2914,
473,
3393,
2279,
2135,
1514,
693,
590,
1766,
1445,
208,
2974,
2578,
3451,
3031,
2797,
2546,
1145,
1712,
2681,
1665,
1465,
1188,
195,
2766,
402,
270,
2259,
2024,
652,
2511,
2712,
2766,
1879,
1737,
3543,
417,
1518,
243,
271,
2267,
2078,
3575,
2509,
3482,
2558,
1744,
804,
733,
1076,
1748,
1152,
654,
1917,
3311,
1115,
285,
3085,
2865,
1993,
1219,
3464,
2937,
1320,
1411,
116,
128,
1457,
1304,
3417,
3406,
2237,
1932,
667,
193,
2773,
2282,
728,
2288,
2873,
2823,
1519,
1572,
3365,
2778,
1375,
1164,
366,
3313,
1682,
2001,
3530,
271,
3355,
2823,
748,
874,
2642,
2512,
650,
425,
3494,
101,
627,
1772,
1098,
809,
2807,
2231,
83,
918,
2063,
2187,
944,
1139,
3634,
3660,
2325,
2362,
1054,
1029,
2627,
1988,
805,
3672,
2932,
2631,
1065,
1386,
3184,
3319,
2137,
1881,
130,
115,
2726,
2092,
1623,
1889,
3022,
2852,
1720,
1626,
433,
3559,
1669,
2475,
791,
173,
3413,
3539,
1026,
2070,
196,
3208,
1957,
2030,
972,
3165,
3162,
2702,
1712,
2137,
3323,
3491,
2029,
2083,
977,
433,
2638,
2154,
1249,
1302,
3495,
3505,
2234,
2162,
633,
627,
3212,
332,
1635,
360,
380,
3293,
2364,
2856,
3637,
411,
3168,
3488,
2739,
1945,
3311,
196,
2285,
2161,
648,
1590,
2348,
3073,
2983,
1103,
1362,
540,
1307,
2544,
1011,
1300,
3756,
49,
2142,
2060,
1065,
710,
3180,
333,
1415,
1255,
508,
3037,
183,
769,
3586,
256,
3770,
399,
2888,
2130,
3594,
454,
3394,
3290,
1733,
2823,
623,
1463,
2950,
3661,
1982,
2869,
3096,
3576,
3550,
2225,
2434,
2035,
2451,
3795,
2886,
2272,
1011,
969,
3057,
3201,
1956,
1877,
1347,
1950,
2864,
2743,
2510,
2037,
971,
115,
2042,
3063,
1964,
1124,
391,
748,
2690,
3084,
1932,
1789,
1105,
1057,
3140,
2322,
1543,
612,
3388,
1405,
1635,
1974,
2464,
2176,
1137,
3726,
2773,
2785,
1736,
1672,
3623,
1384,
2366,
2625,
2409,
1679,
474,
840,
2641,
2560,
1136,
2281,
336,
199,
1669,
2202,
1762,
1542,
386,
3777,
3226,
3015,
1762,
2110,
192,
522,
3387,
2643,
2482,
2219,
295,
3845,
2276,
2874,
1892,
1441,
1234,
764,
3026,
598,
3014,
3345,
1090,
2088,
3419,
3375,
1420,
1648,
1935,
2587,
3098,
374,
3779,
2570,
2196,
2164,
3532,
793,
2842,
2715,
2274,
2688,
1097,
1312,
266,
3640,
2051,
3376,
1321,
981,
568,
3813,
3100,
3424,
941,
2310,
493,
42,
3918,
3354,
2460,
2178,
750,
1145,
3862,
710,
2646,
1839,
1614,
2081,
526,
895,
2207,
2453,
1629,
1715,
1324,
1018,
2608,
391,
2843,
2785,
1936,
2082,
1239,
2925,
3268,
3195,
2478,
3126,
3031,
984,
887,
3743,
49,
2579,
1304,
2396,
23,
486,
2966,
73,
1701,
2257,
2142,
2199,
891,
1525,
2586,
2910,
2256,
2745,
860,
880,
2521,
3649,
3471,
3135,
3084,
2671,
546,
87,
3544,
2944,
2971,
575,
1254,
497,
411,
1038,
3763,
3959,
1760,
2713,
498,
1205,
1339,
1644,
2578,
12,
2565,
2782,
1885,
1327,
3883,
3883,
80,
8,
3006,
3551,
647,
1441,
785,
847,
783,
3555,
2198,
2160,
2129,
1306,
1503,
791,
2592,
3550,
3199,
3227,
2478,
2271,
1042,
3768,
3473,
3914,
2527,
37,
1166,
2612,
787,
958,
1434,
1595,
2681,
2743,
2720,
1875,
691,
2034,
3763,
620,
186,
3762,
3400,
2421,
1356,
1926,
208,
907,
3186,
797,
2295,
3121,
2616,
2045,
1013,
2442,
72,
3794,
3316,
3594,
3046,
93,
597,
1409,
691,
1350,
1015,
419,
3286,
3372,
1284,
2695,
1241,
2618,
63,
4059,
694,
890,
3176,
3960,
2007,
1574,
1131,
2361,
1053,
455,
2968,
260,
2705,
3252,
1734,
2375,
658,
1138,
1143,
763,
3584,
68,
2511,
2870,
2289,
3144,
821,
1334,
3415,
620,
3650,
3180,
3332,
3775,
1691,
2199,
1886,
787,
3845,
839,
3900,
3276,
2458,
2303,
2409,
3539,
3682,
1952,
4098,
870,
728,
79,
2596,
2670,
1842,
1664,
939,
2654,
20,
1246,
1087,
1154,
811,
11,
2771,
1423,
1841,
1948,
2463,
1463,
3199,
647,
4074,
4020,
3674,
292,
2572,
3634,
3097,
2811,
422,
2618,
3713,
3582,
76,
3203,
3993,
3272,
1769,
3043,
1527,
1571,
947,
1793,
2909,
1163,
4184,
431,
3312,
4128,
2322,
2243,
1069,
1782,
1175,
3326,
2361,
939,
3918,
1193,
3507,
3662,
1494,
2574,
1085,
2075,
1818,
2938,
1054,
1155,
970,
1067,
3656,
892,
2098,
2244,
2874,
1917,
2738,
3069,
713,
1514,
473,
221,
723,
294,
2253,
3056,
2751,
2958,
2440,
3053,
1460,
1145,
384,
1357,
1645,
383,
3860,
3743,
2912,
3216,
2235,
3720,
973,
3041,
1816,
2418,
1744,
2229,
581,
3733,
4135,
999,
3392,
1921,
1724,
3551,
3161,
3118,
3401,
2998,
1247,
2306,
890,
1374,
398,
2199,
3007,
119,
3842,
4228,
2784,
3435,
2949,
2875,
2117,
2254,
1693,
1870,
3784,
445,
438,
4266,
229,
1513,
3454,
83,
3448,
3470,
1784,
3899,
2620,
2477,
1759,
2552,
3017,
1698,
130,
982,
54,
197,
413,
968,
3227,
339,
3834,
206,
2824,
3149,
1923,
1848,
1411,
2344,
1446,
3215,
430,
992,
1051,
920,
354,
1519,
3404,
769,
4051,
3301,
2578,
62,
2792,
3354,
1989,
3405,
1569,
2228,
2170,
2149,
1306,
884,
889,
2392,
3738,
1147,
791,
3867,
4046,
49,
3032,
3806,
3368,
4290,
2067,
94,
1623,
2950,
1658,
1835,
2689,
1938,
629,
1445,
896,
255,
624,
1508,
51,
1278,
900,
254,
4071,
862,
3624,
2468,
3137,
3690,
3487,
4292,
941,
2471,
3659,
2508,
2303,
2513,
1561,
1562,
871,
1010,
554,
1022,
3432,
4382,
1188,
1806,
3953,
1954,
4104,
19,
2724,
3839,
3749,
93,
1861,
3775,
3650,
3640,
2611,
2906,
605,
2845,
1897,
2804,
2184,
3946,
2436,
2058,
968,
1543,
1332,
1663,
4048,
1024,
26,
117,
471,
1273,
3795,
696,
4172,
4320,
3314,
449,
3275,
3591,
3277,
3134,
3676,
1364,
1718,
3057,
2725,
3246,
3816,
3371,
1569,
2426,
2118,
2721,
1673,
3621,
1457,
2444,
2399,
2364,
2496,
2741,
1465,
1487,
436,
1465,
2383,
2215,
3778,
785,
597,
698,
327,
1233,
4260,
4270,
202,
457,
577,
1181,
3505,
364,
63,
245,
225,
191,
3156,
434,
3760,
4299,
3674,
4011,
2606,
3711,
3319,
3609,
3283,
4462,
3687,
3806,
2693,
3064,
2826,
154,
2010,
3110,
3191,
3758,
3632,
4292,
2444,
3138,
2140,
3348,
1858,
3831,
2438,
2367,
3168,
2933,
2749,
4019,
2292,
2895,
2131,
2752,
2217,
2656,
1606,
2645,
2175,
3015,
1520,
3204,
1970,
1744,
1776,
2650,
1921,
4503,
1880,
1937,
1760,
2785,
1803,
1355,
416,
1920,
1294,
1548,
1557,
2569,
973,
3083,
2432,
3112,
1502,
2971,
1050,
1319,
2197,
856,
2557,
4053,
4525,
3183,
1908,
2915,
2638,
2203,
1162,
2446,
1924,
3945,
1338,
3064,
2041,
2874,
2712,
2581,
2244,
3442,
2539,
2589,
2279,
2669,
2146,
3609,
1626,
3350,
2469,
2625,
2143,
3895,
2448,
3163,
2011,
2997,
2849,
4487,
2330,
2728,
3142,
2977,
3665,
4256,
2465,
3838,
2914,
4461,
3435,
4116,
1792,
197,
3590,
4549,
4243,
567,
3787,
3932,
3184,
4386,
180,
1526,
1786,
1090,
245,
818,
1178,
884,
3144,
728,
4091,
677,
4581,
1832,
359,
1863,
1044,
1581,
1405,
2629,
1031,
1418,
1987,
1135,
1561,
2771,
916,
2319,
1353,
2438,
1563,
3414,
1259,
2831,
1804,
3032,
2719,
333,
2761,
2519,
3868,
3436,
144,
4223,
1034,
4124,
3340,
4388,
44,
1137,
3503,
1091,
4075,
646,
207,
1172,
93,
488,
99,
2003,
1354,
1876,
4393,
1069,
1595,
1961,
2159,
3238,
1300,
2984,
2159,
2737,
2766,
4624,
1394,
3286,
3895,
4528,
3371,
886,
3215,
3412,
3977,
335,
4501,
1205,
2767,
1331,
664,
1263,
2035,
2250,
656,
1625,
1048,
2255,
1689,
3440,
1434,
3102,
3103,
3131,
3195,
4114,
1790,
2874,
3032,
4176,
3533,
4706,
3559,
338,
387,
403,
282,
1874,
456,
991,
453,
1553,
1375,
4400,
382,
2266,
2398,
3045,
3296,
3311,
2194,
3652,
3150,
3991,
3659,
940,
2998,
1226,
143,
321,
49,
1594,
1129,
674,
1748,
1702,
2164,
2510,
97,
4079,
2516,
2562,
3878,
3376,
2672,
2967,
4528,
209,
4473,
1654,
3762,
51,
729,
1405,
282,
1068,
413,
1116,
2218,
2058,
2042,
2572,
2483,
4022,
3495,
3892,
4663,
1383,
3523,
4332,
4246,
542,
483,
2985,
4166,
1199,
2875,
2643,
2786,
3481,
2313,
3942,
1062,
3066,
2597,
333,
3029,
57,
510,
2078,
810,
1818,
795,
1142,
353,
2183,
2621,
3463,
4672,
2725,
2648,
3722,
3915,
199,
3633,
133,
458,
566,
900,
3013,
920,
1087,
1085,
2555,
2990,
3416,
1570,
3751,
2494,
4312,
4607,
1977,
3911,
1809,
200,
640,
1231,
2794,
1527,
1123,
1988,
2961,
3272,
4836,
1421,
33,
3710,
1205,
1258,
639,
4147,
1734,
1347,
2620,
2497,
4449,
2519,
4180,
2921,
4713,
4871,
1190,
1420,
462,
822,
1474,
1569,
2781,
1012,
2658,
2043,
2832,
4511,
4871,
3378,
3941,
31,
416,
501,
2912,
769,
1045,
2162,
3704,
3558,
3095,
2971,
4284,
3292,
4843,
4483,
1922,
4381,
2068,
2575,
3265,
2536,
3763,
2632,
3185,
4375,
770,
4562,
2405,
3129,
1049,
1227,
2996,
2771,
3151,
2729,
3951,
3702,
4562,
4364,
1468,
4423,
1111,
1833,
2433,
2404,
4365,
2785,
3569,
3431,
4820,
4766,
632,
3885,
2675,
1009,
2010,
2261,
4033,
2816,
3165,
3747,
3587,
3737,
2101,
4452,
1477,
1858,
3158,
2898,
3270,
1863,
3820,
3496,
3489,
986,
1809,
308,
1158,
1893,
3378,
2392,
3700,
2532,
2865,
4966,
4357,
4816,
2384,
260,
1850,
1288,
2891,
4642,
2998,
3258,
3804,
4212,
529,
4696,
3575,
1443,
1939,
4077,
3739,
3503,
1233,
4964,
3977,
68};
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%d\n",ans[n]);
    }
}