c = [1, 0, 1, 2, 4, 6, 10, 14, 21, 29, 41, 55, 76, 100, 134, 175, 230, 296, 384, 489, 626, 791, 1001, 1254, 1574, 1957, 2435, 3009, 3717, 4564, 5603, 6841, 8348, 10142, 12309, 14882, 17976, 21636, 26014, 31184, 37337, 44582, 53173, 63260, 75174, 89133, 105557, 124753, 147272, 173524, 204225, 239942, 281588, 329930, 386154, 451275, 526822, 614153, 715219, 831819, 966466, 1121504, 1300155, 1505498, 1741629, 2012557, 2323519, 2679688, 3087734, 3554344, 4087967, 4697204, 5392782, 6185688, 7089499, 8118263, 9289090, 10619862, 12132163, 13848649, 15796475, 18004326, 20506254, 23338468, 26543659, 30167356, 34262961, 38887672, 44108108, 49995924, 56634172, 64112358, 72533806, 82010176, 92669719, 104651418, 118114303, 133230929, 150198135, 169229874, 190569291, 214481125, 241265378, 271248949, 304801364, 342325708, 384276335, 431149388, 483502843, 541946239, 607163745, 679903202, 761002155, 851376627, 952050664, 64144443, 188908240, 327710068, 482074135, 653668657, 844349552, 56148036, 291320897, 552338226, 841940485, 163127330, 519222670, 913864273, 351078571, 835271841, 371315364, 964539468, 620830846, 346629462, 149040638, 35836012, 15581609, 97644938, 292341746, 610949803, 65878029, 670689095, 440293193, 390982616, 540654290, 908857840, 517052409, 388671767, 549419265, 27354940, 853235032, 60624266, 686288077, 770335945, 356672859, 493181634, 232243247, 630964208, 751778185, 662727875, 438158716, 159067600, 913903733, 798994935, 919474202, 389799050, 334821255, 890418652, 204731154, 438923364, 768615211, 384799940, 495497302, 326857360, 125071970, 157694784, 715853957, 115827540, 701601657, 846748744, 957386147, 474406537, 876902589, 684811254, 462873569, 823766839, 432684175, 11033307, 341735784, 273588935, 727392423, 701087911, 276842453, 627090292, 22725282, 840194912, 570967892, 829857053, 365960282, 72406602, 999001583, 363628350, 566853084, 205252034, 88278364, 253816664, 987661685, 841656047, 656171256, 581242678, 102510429, 65815171, 707128517, 681152865, 95835244, 545600796, 151141485, 597991706, 182390474, 856024133, 278860630, 871012421, 873584935, 408735550, 549735571, 390472534, 126080017, 133319642, 63342335, 934575330, 239411137, 51475971, 148277980, 135012686, 585509317, 185015790, 892123146, 103340943, 839035764, 933018550, 245981558, 883751257, 442210042, 258407041, 691482375, 411431619, 721206481, 888573214, 515297589, 918325172, 552749129, 449423521, 699367954, 955881029, 989109427, 261876701, 564310538, 673892295, 81427824, 747231859, 931290658, 59165603, 670910463, 412156755, 118367033, 948631051, 624108816, 724489536, 101983039, 363120786, 482579737, 496019939, 341315714, 791631857, 555284206, 482204314, 957876119, 420721322, 90315635, 838289299, 296312013, 128802177, 572259033, 164417423, 773357051, 845028037, 988203691, 810504042, 134007967, 499051378, 95161114, 22367817, 33113074, 652589660, 839817173, 81672369, 95434880, 26153628, 328731303, 215121552, 871952027, 322886696, 157947521, 997773316, 933344945, 802922184, 566449370, 632856529, 422151160, 11248034, 168899947, 622454962, 887146225, 494487294, 978279754, 448655676, 142860862, 777559696, 124048602, 625834151, 515827241, 247563035, 736718156, 223171521, 292198373, 861594339, 719778081, 418929100, 158836931, 464229654, 346277329, 751057836, 46119413, 349321584, 517051996, 599675069, 653137758, 720467541, 951036742, 679567266, 519048286, 301270857, 13298697, 578817846, 736232464, 881505280, 240958212, 266311154, 741050660, 520091789, 528158869, 974447655, 558437286, 667717778, 506287441, 205601512, 36979115, 837997590, 969200359, 985297085, 553937658, 889753180, 475595307, 435384833, 592940083, 694049605, 114244520, 659772952, 101860954, 201237207, 212356814, 796796329, 719198067, 452720589, 490899369, 718032001, 101229949, 314029949, 67627612, 52977540, 835873405, 941039584, 90955911, 214144061, 875281247, 170835446, 500626410, 743701211, 84580353, 567232155, 543615256, 713660336, 940353248, 234541133, 214631870, 223080220, 641319553, 470772346, 87344085, 231944258, 651411897, 571461116, 78259738, 846064047, 123793166, 825364573, 663434613, 750266882, 841727091, 416104414, 234449169, 551623583, 352325848, 994855672, 647242358, 372476860, 573326095, 415915618, 614653519, 283987849, 292994859, 271993996, 185234607, 458271253, 518538771, 20156574, 69753465, 495672636, 506858420, 96225575, 192185958, 829778499, 694227291, 891920280, 418748077, 502033377, 247621379, 911582662, 120244659, 408383445, 323150967, 516920709, 135391054, 92955794, 850884661, 690043327, 787760467, 850432497, 829222345, 740625385, 15614419, 335458129, 131486579, 483386723, 390391958, 966861239, 584657277, 581043531, 90730386, 172006621, 59614549, 16442128, 905771188, 291113578, 804511312, 271353159, 615558416, 415637827, 452335762, 580115851, 31968185, 449767484, 415921037, 709517132, 119560882, 445774367, 521448823, 331714091, 602412852, 39685156, 331133059, 533682250, 624489490, 368637253, 665220400, 971813573, 945846117, 165086309, 607422324, 821968753, 627486548, 253362690, 686021098, 227257598, 12690063, 13122343, 702747223, 322933528, 344698145, 939960189, 168879715, 796716838, 80396536, 700890864, 371847025, 824304061, 692301321, 96516490, 687768922, 178253993, 283001166, 244550544, 911268612, 659325550, 284769811, 622818631, 823333585, 531185347, 254563139, 722462010, 668495387, 908655935, 768342867, 154140741, 547886488, 329522119, 129034920, 270457324, 771670750, 551513369, 170030212, 280253987, 440993697, 643103641, 57041501, 577824681, 943822960, 490950542, 672092941, 275223819, 510026396, 194660444, 582858995, 884239765, 414863030, 57296410, 296077350, 425407031, 714421766, 200218635, 245058478, 160463919, 434464614, 40647448, 787123949, 683146540, 511054584, 180965172, 930563003, 495421687, 948034922, 12177100, 434769077, 812536072, 743324554, 682543895, 176304316, 748643014, 636694013, 343587920, 119370773, 240930692, 14969773, 844863841, 535725281, 930913504, 780641565, 285773398, 419201880, 850352242, 504705350, 72417917, 242994846, 632042435, 244843329, 952866118, 551831168, 235350789, 325677800, 62752531, 309790088, 908838342, 358080734, 229489439, 444973341, 134260464, 836126521, 675113513, 159487095, 914719944, 814938851, 505009846, 68941369, 102909059, 119454910, 712380280, 194818539, 420153845, 507875747, 326870225, 504609466, 856337127, 978594649, 692516029, 915554773, 964609201, 285833434, 369564429, 741788303, 45214156, 43104136, 203462526, 225555463, 737831034, 182035153, 431858146, 652058583, 520134026, 550345284, 256451329, 799455983, 13134583, 46304874, 753890352, 370198909, 79047840, 902338289, 491537687, 666795522, 565769099, 276537261, 639741870, 126480658, 277726220, 960332186, 313416384, 105073680, 576787071, 235748918, 999087166, 83487253, 754147020, 599200232, 229340458, 60611762, 674125988, 432120997, 296699309, 719044504, 291671586, 64115546, 423944587, 152220610, 458226602, 964306499, 690579491, 295508752, 113840177, 340591920, 668860, 378919300, 596891528, 45212932, 960399915, 139975537, 217609843, 576018124, 146965607, 641298863, 259761346, 869836149, 188844667, 284493151, 787432725, 578995269, 300667466, 131159996, 204484792, 365256255, 980674043, 770648409, 731903600, 37310047, 639806336, 469178976, 551275712, 335277035, 814969742, 858070867, 748201774, 149723291, 742378283, 962743904, 251625809, 935360773, 360667962, 819958817, 931303781, 719321377, 986513976, 879546975, 133662627, 891931661, 768192563, 168701696, 566011737, 273114191, 119977953, 149426280, 820033179, 520850728, 275604396, 590913039, 203955190, 753001366, 962372716, 919043485, 42921879, 541760747, 378159548, 676032064, 160383648, 134495112, 692440548, 695985069, 877806228, 487008728, 850827350, 852959267, 630369518, 594118820, 987051063, 433524391, 67841901, 430989994, 492887788, 348639684, 375124584, 640548969, 403920792, 278089796, 327563016, 624817254, 500202051, 976617942, 612955548, 516482078, 616901560, 521254661, 15037601, 303151879, 10694729, 731495490, 369862238, 113691039, 110009001, 861263789, 472243984, 646391254, 631710227, 361495394, 473355188, 942815863, 527080226, 35773639, 562688039, 667451296, 798893412, 738904153, 967417420, 521327757, 551766172, 865893370, 423167891, 672119133, 302189056, 541878906, 300370037, 262860990, 5113419, 270050111, 284894839, 17708074, 911095102, 30193905, 907755558, 556797296, 312368446, 393495401, 935469324, 126508925, 842525696, 777319302, 514541491, 442361917, 839659970, 316137329, 19423339, 229308158, 8032539, 910374489, 607705700, 149825485, 532949105, 115265777, 504538788, 249031286, 308254079, 462335881, 855962632, 665153863, 187396157, 981367675, 685584276, 984725035, 935191291, 25748707, 919691191, 662209482, 454661691, 404573719, 948352804, 627435596, 995372463, 187803707, 23088667, 346344928, 556488919, 37068911, 311661863, 955122977, 886115328, 86435446, 735665248, 289149818, 296129454, 265314915, 762253372, 746065953, 663997022, 851606169, 380823822, 429357045, 794128029, 735999519, 393715653, 91757192, 400541930, 353533284, 226396441, 317191680, 571574495, 133808336, 172986654, 387320632, 174747741, 617395663, 539360650, 477651917, 700729095, 391335914, 919087525, 436549552, 296920328, 494974054, 399779721, 294670798, 671878706, 174046151, 197967641, 200208910, 746034063, 709029137, 425028370, 451340345, 275067012, 962154303, 339934079, 955439225, 379632266, 648200593, 281077637, 127474218, 526714895, 733245452, 358674445, 412238182, 197411318, 734071137, 990340179, 711217633, 656840111, 999611911, 661353714, 808284228, 894407805, 925759562, 706015166, 776790462, 460976543, 251005044, 296595587, 369658665, 890210026, 523559, 123439125, 16589117, 90733341, 478184167, 66796687, 700290302, 79296082, 917066187, 939542074, 375028904, 274475626, 689062578, 144632280, 235571489, 164936557, 238994018, 952720065, 134441529, 613302676, 703543316, 301195050, 878422708, 843049829, 800766400, 295943224, 420603853, 940533312, 367470933, 942935015, 667504225, 367242832, 187667870, 162997215, 330432177, 635800879, 163486389, 182583201, 43689117, 996424559, 599447968, 615567373, 435298398, 682552670, 633261596, 798675683, 724609476, 569498590, 227517943, 180794961, 944005787, 807726322, 519900537, 799570321, 569625891, 677703322, 943176251, 565171010, 191631595, 57982305, 56699979, 404817779, 542442204, 211568089, 932140613, 162065517, 68252154, 756329410, 115461101, 518697274, 377560070, 960260938, 46474118, 214491072, 752940651, 785378163, 941371470, 91230064, 534961551, 828141406, 89799673, 791385456, 227433867, 228956853, 451432205, 469943829, 709496665]
t = int(input())
for i in range(t):
    n = int(input())
    print(c[n])