P14020 [HackerEarth] Once a Mathematician was trapped by military people during a world war with his forty colleagues. The colleagues were without any weapons, only the mathematician had a knife. And with no
普及
题目描述

Once a Mathematician was trapped by military people during a world war with his forty colleagues. The colleagues were without any weapons, only the mathematician had a knife. And with no weapons they were not able to fight with the military, so they decided to kill themselves rather than being killed by military.
They all decided that they will stand in a circle and the every third person will
kill himself but the mathematician didn't like this idea and had no intention
of killing himself. He calculates where should he stand so that he is the last one left. You have to tell the serial number of last man standing.
Note:- Instead of every 3rd position it will be every 2nd position and of course the number of colleagues will be much more than 40.

Input:-
The first line of input is an integer N that specifies the number of test cases. After that every line contains an integer X which is the number of colleagues.

Output:-
For each test case generate a line containing the position of the colleague who survives. Assume that the colleagues have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2.

Constraints:-
1 ≤ N ≤ 1000
5 ≤ X ≤ 100000000

SAMPLE INPUT
4
5
11
45
23987443

SAMPLE OUTPUT
3
7
27
14420455

Explanation

Taking the case of the first test case if there are 5 participants in the circle, the first to go is 2, followed by 4, followed by 1, followed by 5 which leaves 3 at the end.

输入格式

见题面

输出格式

见题面

样例输入
880 56733536 86490977 79553416 36985321 11086830 95548856 72189915 59190978 70048426 426220 53630037 29016399 76126438 29995296 73913177 50163456 1925581 36770113 53453198 14293189 38114987 28195216 224395 90468271 49531085 97545259 83339004 15722124 74894762 40444441 48595038 7880439 63834092 14399379 32046366 24852794 2635961 93286401 31777788 31104102 56203368 68846240 47005075 40164324 82070564 52711287 89842778 26315932 4414438 74648672 19330306 5555412 4386449 37472524 4930865 12518565 52170627 75454775 28670369 56967164 98156412 39518196 46667604 54341983 88104957 16843431 14183151 25926226 85410195 55623183 22112299 31429696 16914178 43004416 57772471 70100136 27837197 45601815 52231655 68302867 38967263 12522582 13180173 80909679 59775969 17638552 27178127 27369849 7920452 11808054 52048932 28510318 47422324 54638386 70662491 84096101 64585976 95395948 51475203 6064408 13961592 61406672 63752000 48670519 77255168 19163055 25443203 11978681 37346928 85111227 60195866 68716081 53029442 12731102 89960774 46046177 40794398 55890562 77717951 79581509 16221587 13356908 9863108 15402013 20367904 13145041 31571014 49283450 50204562 5130714 89994204 30992090 12788958 35072637 94613339 97167664 17576165 35258285 20199641 34912277 1317340 53884016 94042995 88471104 91872798 98257599 86055380 22712362 29145757 52982243 75971298 27251285 97578481 89894464 92244801 79422799 1124371 23007010 75417632 73453855 37543004 8416658 27318673 76244114 61162977 65328128 69627691 45331075 36215014 26712071 57160026 63175587 40259684 94400696 78133443 44166637 45234039 54396895 61893928 6700082 27769926 41001079 45764027 52695594 77667395 27064801 86041240 87066897 383059 7128944 27729945 82548155 538611 87111578 7337864 75287156 8243145 50265864 52093316 26392053 69600543 8272706 84868021 70048652 52433827 73837701 7875605 93548726 11511452 68941517 89161243 275645 26024676 79966231 49132820 30729553 45360799 30883814 77933282 56626981 29399005 99181650 8057803 33551006 64846788 49346780 82445913 66840207 62138360 68369373 86849180 18517239 10921198 53055478 5548862 83640200 34638684 18677565 24565951 44470185 59962104 80111223 92821145 86283381 10638186 64923504 32816401 17154180 78574245 25376694 43314109 37909932 567708 9386845 46566442 83723433 8804993 63859021 51513869 74008918 35824698 60054205 71553542 62384179 79483273 67582418 69702786 27406708 13918761 60957843 5308619 42175760 12125943 24706928 91589950 5640686 11221178 7353538 89141987 26898343 13790588 43494887 20703039 89621277 91255970 79689128 3946242 69043392 55655136 55286383 75300479 8203284 96446504 95023184 9952324 23127162 75678469 51771868 28518095 79355212 36945815 33363936 30624138 94005719 64944038 30301353 67982780 26216442 30827298 38323546 34746212 36935526 47242163 98279657 60511167 79733822 94149614 91537135 93369083 43356710 14443803 24772371 96664687 36095247 59290302 21860565 84866144 18834473 99051159 1082915 88737893 5240554 84570201 1043858 94612474 66062128 66119557 32446595 7248846 78874571 47352481 71741902 87545524 93903267 14347602 22246141 96865839 17266700 89627078 96167559 24946914 12165323 37359899 32522640 61224283 6821899 53446817 18791212 8127098 70200866 70742173 9515339 47076928 16727307 21517735 8952377 45701622 67478184 5660051 25061435 70919047 14254877 1386094 70089504 23296935 68563801 77109753 29280522 7399351 62831600 2788660 69680023 5388532 91774474 9582237 49083548 94560275 45984841 13464312 84335121 71053028 79770798 19520520 38785236 36783868 66972255 96511949 67746698 13074970 23414286 10287774 46133947 94321752 49012843 73314584 67218079 42200591 19032630 22981990 82910077 44261954 54192761 93980208 85154647 83170298 39409345 56749889 51916864 88383078 58440815 51378678 24454749 96162906 47912252 80410647 9973504 28013091 23768810 71725887 48933183 59487844 75028152 86299366 81329072 64742683 15665955 53358509 20436039 62741656 27654936 29112904 36322085 42751093 8406601 98953501 17087515 58609427 46093359 69871291 12333330 7436008 568386 60184986 79765445 53149100 19594460 55563996 30455656 32610904 75384655 27656585 37616441 96155643 32242898 17573600 2873628 38000278 19220530 46462897 82451034 63826989 95578737 56897878 46693822 5686167 74802997 31660906 64045311 49024448 17458396 55624958 49125444 70905181 87950365 34503787 8313063 39094195 39564133 10355170 61080668 49360367 33637540 54896548 32852798 52773989 73613753 3811193 72037923 61602006 13642193 43357916 1483124 78708093 52330046 7368447 60711290 14292570 2446843 85728717 76406635 51626401 29526332 79527227 45307295 73881452 82269526 4139325 50535681 85425263 37459402 71558654 66096148 94109659 59682573 18115457 62707279 13392880 20717583 34362938 82459220 48574867 43985605 68543943 50217082 93658970 1339929 26062382 2364681 91765864 6662082 41911129 81339472 61057670 96458622 75013349 9524460 32292078 56714821 24465135 76258793 35195690 83407162 71703633 68945825 77560660 61870757 38941272 92303077 39052520 13100177 23516540 25448007 56951640 92802981 65169181 88652311 86119267 28845579 48166778 36924621 19446348 99819950 68510675 17959907 78581185 75144023 50212755 9350369 67027626 24696356 68245007 36911979 70174334 84037224 42969925 5038187 9380737 20434958 22413279 82853297 38848209 67077806 74197617 9916338 93329297 49279212 44635295 29035126 88791343 43289367 51646088 69359769 46690892 1096215 8393196 19485491 99215329 60404638 4059152 46645285 41428677 84425754 59730649 81159694 22325749 74846599 73780755 4606288 73540234 90781921 64387630 42019494 88845908 54111019 4550847 66411843 10102775 36373657 37254948 77315477 58999123 56504544 85879900 47664075 84368257 58840667 71178966 16234851 31448996 46557752 69210539 8956280 97575312 79639108 91541118 29241989 30462851 99614179 13166807 56596417 87813982 91553725 20625720 75688328 38141722 17168391 33174401 9076899 81322622 9870746 62803771 32212454 31942907 28942448 37146354 43397021 95502636 40416097 95566230 92746236 26177716 29242756 88323838 63475932 41459313 89252787 87604916 61358502 91354877 20477836 13533338 15365592 99445325 29026293 38892892 61061204 53715838 38991964 4058051 92636125 23220809 32961355 85305249 91994579 95885168 56657237 27508445 62036630 47317803 68753595 31869804 21323115 29740738 13901478 97877929 86119297 23958120 4932210 72111520 95655384 56810281 842721 59501746 5004043 59002607 21550632 10774655 97725207 42400992 75446045 68451251 76745713 28795224 66286061 56067342 58483893 42691279 97069273 59312731 91537839 63464515 52099216 93519196 89061858 5229471 22489189 10832822 53858956 28910720 60259935 16114599 56439152 11963865 73312336 35583157 54193070 96309494 38980173 66811593 69598974 75603615 16895237 7671210 25967489 55515244 8806410 5227712 64295976 51574947 7599973 59511017 17121003 50748596 98195707 58322232 4383864 29453402 79976611 31355336 27180473 95745369 23142191 59836625 58501313 79933632 27410041 40013692 93571974 81937948 51339836 44376561 58653302 46637097 97409816 51065538 68179931 30349058 69634255 51948799 18462730 13893061 68418820 64794858 78895357 90314366 95410646 25300911 19543363 88633047 41346937 48377688 57852962 24093989 42767077 1346626 920819 74607594 63296210 90533837 26905804 81051144 17699138 6571706 83240107 71371487 7016279 5578246 69184232 72700211 7735979 7353729 3026597 49388297 59685618 51181224 79575535 18840591 15610126 33341148 30983818 53810629 57599887 81210803 71511317 56624572 32265211 65243365 25751628 22658345 54483754 12210295 71233869 98072778 89931518 43749553 42877337 2222537 93649876 94432325 36678047 3315103 8346319 27416937 65577711 73587404 20558017 60232772 57422969 3249651 21501174 45369425 55267292 79892205 22667790 17992591 54064654 92687728 74362481 37923168 8491820 62046982 30787714 4341764 25829996 98225514 38716829 79051401 8970785 33735984 98670821
样例输出
9467745 10475025 19528133 30569433 1103691 4879097 19002359 27363329 5220369 11295309 65574489 61484301 31708051 4207549 2273063 63296609 36987923 25858889 6256427 61747267 314409 37627511 55552221 6083461 27752115 52654721 19586521 26024767 19408881 10654499 5178789 33201939 1084531 857953 33275553 382237 15576359 52819877 46391573 40739825 5359179 39127643 3027369 12155001 19308723 2812195 43140635 49496791 2669979 53629449 42057643 24447247 56254339 52040633 55236971 5990195 28455011 1273587 14975927 57169045 66937595 16788881 131045 18542911 32000683 41667409 54042341 14549763 64688553 8163759 23842309 41592735 899597 58231783 27118649 14143793 41390611 6378623 29904733 16026983 56151515 8885019 15209431 38529637 3556551 17510603 63828411 2308359 29802009 34834865 2611511 37859633 45084249 23272755 63001157 65038717 20190227 32008627 6848719 12318521 6846743 53060841 12886479 63253423 52861333 2703281 33454589 21768545 39466901 7188293 654797 14493881 5729273 43569577 3326039 58941881 47571875 32523999 35736063 38827707 20512175 8179579 42875595 2682027 49925303 56719123 2835867 16991825 60631437 141703 43063991 4625809 14323931 231427 41700457 14491969 1091853 30251179 56298363 34115079 61028363 14836517 2961321 8788797 15075333 6901553 25808663 11736047 34334389 44498069 49942065 50051989 60834445 58678579 37026995 44026867 10728379 2306971 954957 7637879 2392699 28658039 9194497 39836843 6477203 2376169 49505845 24724919 2408801 14996129 42316755 1106601 51090411 1612553 59950529 23385301 10945623 28965139 33341081 64384349 55302991 42599821 47509197 16005569 43893239 2803013 23926861 66982761 7082489 17732401 48938683 14784189 13478133 19376641 52832387 15214993 10351293 15058595 15834447 11208311 49629849 29035401 27227397 47471787 16695765 49070965 64754231 32764247 2026551 14878673 1095643 12102893 36092963 38772943 65523373 15146621 32198555 13622897 62098737 3766681 55543725 6974235 11831533 2958581 48463537 62297037 51558121 10132091 45610129 1624515 22804899 62969161 43443121 19269417 56871041 20589537 372555 15542189 27109935 40530351 12052111 31015425 20731549 34005015 20171617 8330355 1050933 11486629 55958869 14813461 27173351 66712419 32598399 316139 6116703 4959145 61802005 20314387 52476849 52755891 9332035 44002445 23109935 16582573 24024327 28299299 7108513 59478835 17929071 47702917 7794339 45762505 28618047 43681901 327439 4001217 14415283 62819685 59650373 39501999 25032875 22592245 7806893 40986541 24167229 21552283 11666249 7002779 47336877 32618695 12903613 46024461 20125809 36235485 8520643 41546699 5835447 1350065 19364077 41891635 1405615 65445017 63100053 33532059 48124839 23601891 1442845 35034717 21258205 4108751 34804705 15077243 1140977 45521203 876747 2446243 44976915 18930335 54522733 3444175 31862293 65218987 46383527 1250805 42248667 53639081 16909499 21340725 28999889 2053829 7319463 2126865 623707 27424449 43833737 28071443 12281925 59019497 44560805 63831871 16408757 14892975 3866305 2696743 17036181 46434509 24962413 27105263 2537387 701407 16740461 13878659 25621461 40500745 3737761 7996003 55330213 19830883 85757 4914873 61529589 27447885 40922033 20038133 55471677 19310869 4333629 15608689 49857759 11951739 912549 32199601 4755961 11531547 322011 4192945 28307501 369767 22076179 28294175 24362617 2235901 26959815 1454205 38575687 22065547 2791381 3967071 670141 23328605 56388953 8357647 48710873 63930751 13103387 58631777 31959387 30784705 15691319 7453583 15850331 27944657 6009585 42626567 19862675 41833795 17327383 29048639 13488695 3584065 42544665 16666109 4273293 24168251 63660449 20322557 12648239 25314937 19626867 6335671 11274667 28435207 5468467 10721033 29662999 36767749 42702261 13856309 42787023 22685691 10150751 24764711 30405159 20748667 7897281 14208781 32501153 4789951 25826585 60391975 38829347 4586003 52251063 16161587 5287711 47140813 37418657 5724527 60153725 16520307 64421461 6015319 53355419 54877323 1387179 4323191 33298353 16632085 19153265 16745003 10165759 11869869 643861 7241119 32036025 65687159 2843009 43906759 53000219 43615191 28949149 4731395 14301195 22304789 1485485 7313891 24702489 7890325 18581399 47961511 42753241 4667123 54782587 28135499 44803451 11026047 10640971 25637585 237387 1497509 36380813 32699617 28002081 39078059 31576417 6765669 30206999 48370739 47672661 14229015 21440493 64222913 33967263 2549539 32041995 5406479 47673807 13137715 30959659 2998367 4316751 63876533 54295547 36922719 27461191 38596101 30122469 7851473 9229155 27540629 23160349 21385073 30355471 39988747 51243 9362595 21454611 35185873 21220963 52178103 32483295 29723929 5011099 60171551 10131927 45982465 13121029 11435759 4130529 1935223 17323557 535245 11562543 18135879 14464887 18216919 60129331 8576457 21651311 31101441 40679369 24438677 10296955 5998485 14315935 20877817 11238661 55026491 15423327 65092697 55967579 49142743 17236181 11752483 36057761 36348843 31174951 56474301 11282117 13694363 64696041 14943243 33413799 12483991 60674633 60276843 55320789 60634627 6466855 19022717 64885123 51696819 45444223 19023703 37922229 28899689 35846713 7299 3508543 53326259 22509581 37895619 46258833 14156967 50685517 62967921 24387333 61229983 10093149 14981755 2239299 10481299 4791707 48005753 3325125 3495027 2291405 13700101 8538629 32496447 54903025 25277447 25246255 14397065 31718563 26169669 45098313 26297293 32507801 3512913 48502365 4740217 14574815 45495371 4262765 15891059 2556715 46832369 54185727 22394729 304617 37487197 15680509 9897705 7044731 36740835 28235621 8642505 41418047 281001 19994653 3382259 15913377 23704307 2303909 39220907 16429251 51201649 1796703 24630319 59159515 35846459 4247589 4806593 26062665 65701683 8770885 8029439 13451531 54041633 8856641 486747 46301069 6860351 4009535 53187107 2746433 49639317 18145861 12641117 14988447 8198467 7083233 11304277 53119049 14592497 28113591 1425233 60430123 21378027 41530079 16916601 22788297 16157329 44361165 65068499 45611455 66301103 35916607 60952583 45413717 4942871 24120793 23695525 32178501 8083091 15364803 51063673 53581225 3200145 13695051 30524767 39829239 59255477 246173 32698125 56025315 15904119 22908351 28178579 1824325 28136631 25006741 4389189 46374341 29211525 18016379 54687479 44453343 17530741 66929047 50398545 54843925 22849005 62378845 44056297 23681963 27929611 49279485 6522377 2077557 13868025 40272001 61920077 20449199 18507791 15624303 26244799 17533491 33102365 58075469 49058825 18809201 169583 38890077 60163299 18358539 31664501 35425035 40736859 55286997 34565233 59787625 26925783 265665 363513 31385971 24350983 2146715 45942123 64791167 41918001 50200051 18248209 24864327 44909735 10403159 9225699 18652619 29867739 7032897 1666157 8070629 29180753 14954529 1886017 63072457 42119821 51856355 50950579 45545815 3704895 54323999 23424635 7150031 18259483 19873845 4730291 61449859 38620667 14793319 42469649 51836673 25410213 5930897 7675935 52390157 19854243 57527317 32827343 29426451 15654401 22002719 25331105 15070603 9614579 31550617 46449649 42479769 30862297 22174031 4527363 54233601 22246191 21355615 8508065 4253959 916281 24732527 5603329 15195465 22327701 10081365 28728957 40629531 54489261 146745 7151153 48050967 40510709 62413449 18694069 47409309 38933293 50556913 56984373 12703151 9479209 57878055 2838697 63479633 20330855 6000119 617767 33215383 37479865 26651519 60106305 56178479 13763359 6884883 24096231