P15908 [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 tried to calculate where should he stand so that he is the last one left.
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 colleagues 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

输入格式

见题面

输出格式

见题面

样例输入
934 48171068 63138680 25597136 5610719 22559303 19374620 52609147 76485130 4119341 84687324 74124384 29214349 76525070 27296334 62086857 7062292 70121510 32711240 40766945 75911566 64205975 68575226 83591193 54443307 63540837 4289505 8767969 70478582 7243533 39723966 78096030 72637160 25590127 54716612 66633208 1112079 15801013 28023375 53733563 65083423 9590222 62245841 96076723 54307235 85757911 29096993 3631332 27612739 42715304 92012779 12703562 34573126 82824689 52997962 92209738 79438089 29359227 91936946 82330820 94119502 14980423 67087425 91654350 3534741 33102806 39544996 80407982 28601519 91115207 6001444 59324612 45972080 23346317 48985952 16795103 26136955 14437051 63486233 36816186 70918883 73342090 63093424 76060920 92676864 42226280 47324849 19951724 99491939 27118173 78043310 40996013 94440834 17395135 25163362 17938318 39144715 96842895 31994713 79275426 1332160 17155664 35594045 19026575 4518671 19818066 26904118 98596004 3230256 97289749 56106249 41386736 45857527 43151267 9178991 45465649 76179730 28817312 88940082 86020320 94417549 79329043 97193224 26157831 75486442 81329957 74970357 7550285 88526347 70680176 15618132 29198931 8956167 37642342 56657427 50046791 99451211 47622542 8894560 4446364 77653179 23068530 51714181 16153159 64511763 67109719 58844618 45135808 3712140 90410697 67500933 79654906 43251972 30113148 24825319 42418636 1769342 96656888 91825205 4460397 88252369 89655318 8723612 24852553 43126508 46522953 2882828 51369579 32308117 88261812 2417293 9090904 13599440 70456918 98684809 65131254 38179862 75137514 94948422 43741296 15605760 51070858 4360551 69037068 72919127 56853478 64726558 56110371 53186219 96415194 37713005 62057954 76940946 55265558 82061388 23506159 86858623 47842123 36487709 24717639 23225475 91083013 77929571 36243410 91648087 19254091 47933320 88224333 63477571 94045343 2221960 33809020 78661329 7863472 57545236 68346786 76765026 92431261 43054802 29128958 88343741 74381658 16213548 33916375 4443993 22646127 33728978 1432966 15578884 39247921 82153776 91481779 29076356 96301379 63851020 15892984 65662749 80391277 27308272 49298128 75237863 88441243 96804182 37450491 68969724 37775868 57567912 27708226 62766811 20200009 33695901 12655473 70186459 68471920 75597316 91829143 47856667 3614396 98880363 8518035 40200269 36609115 71944404 6194066 61604026 62245105 88870597 53656876 77773958 36178752 44606893 29068822 80750867 34945843 86727685 71211160 54560693 59789919 18876595 61818022 58210235 27345805 51558229 99061400 52203434 1165965 46233144 54180842 7978760 2264560 75321934 83190720 61829453 34433500 44060896 7184366 28338400 96728623 88619704 75457138 81662228 83972717 93210971 61033765 78381898 77418804 1069752 83438743 48740796 34821705 58992774 13627750 12905141 60833879 71609099 59542904 45283370 19404149 20814240 17103805 85641752 6533655 62603358 56203454 98820376 87479351 35792012 43561028 5579615 94753103 65879026 51409743 34203121 8931072 2171198 48968033 66008853 43767464 28501811 77393557 12285889 89651351 51312022 7815184 83177593 42438994 73246920 95036718 18677949 77590984 78454648 85934468 29222850 70530422 91636900 41081589 1166026 219483 69468252 5722679 9378507 62879411 6695454 64872965 66270379 91475531 22381678 69625349 18928246 64110139 13947833 50010599 18924284 51840768 61317575 11765480 63266718 79866201 77149093 8427510 87472599 47939759 46174031 94940071 96560224 48773654 24698483 2560912 46895160 70852250 43052677 39734574 26118452 42946004 67368252 28830967 1852432 22224050 59898587 31674759 68337432 47389677 82959179 77234615 30069261 55261207 5645160 74871572 45462917 32456534 31568809 83729833 93004085 16458631 53721951 13478817 32490266 1970484 21793626 54675088 24947867 25212635 23780272 67250023 32526702 96286223 49471751 93979205 5235617 78697554 99692477 96009451 29365077 85821696 24768446 82818165 41213234 94318198 91504354 68784069 91396397 64333339 17332328 72602581 90342039 39090247 11422629 42108723 18050067 43409519 31973030 43708499 72822958 49201929 18119547 6837898 26814370 5361611 63071733 18947114 186603 93789218 72759988 48411723 96048653 62697148 90498526 64971988 85500694 93585164 43941871 82950909 63593627 79343180 57359742 97446065 95754487 97948040 84557479 54240002 57963168 89878623 54600727 15538833 2031064 35797104 23216741 8811884 44482823 59141589 14373609 81821433 20649944 59038908 22052661 1053811 39897985 17106407 53834258 2391512 69178659 1262389 20434816 26335014 41250486 81962111 28917758 37350366 86230746 84085310 46225193 29953936 92932199 67137469 54583945 87121032 2863330 80659644 51171293 52866496 85381537 20708369 35159877 20033257 87798714 32658340 15324532 36761990 28594220 69145293 49886406 7018981 7379275 53259006 34247312 71496269 73685577 11494869 53388920 80387453 17504527 57733904 95382775 81650516 68493210 16436963 87979020 8265372 51724471 32097306 6957872 34399969 16225914 75155969 67333463 87881520 78452126 88963321 42299287 75038220 25140872 52243054 80046662 80550819 44386835 29820869 54286303 51055447 57191423 27235674 54609354 51583012 69269998 58739870 37918698 2529279 37142054 33652878 74457331 25526523 63280545 31075417 51543573 33713537 17915179 7770020 89010224 73834762 50056556 63769338 4912009 43450428 91271047 19030189 42528289 16909673 57610321 11320748 2608603 94874651 26981731 28711819 95594104 87014816 99817985 14252420 3062580 54510464 88050190 7881758 20309437 24761831 46116824 95243184 40404463 69385682 97061858 77408159 76931295 28946968 98257763 88866052 54943876 41096618 48925095 69509174 54507713 77791022 8280361 77124400 39290588 52363258 90551102 37557070 49603530 97976006 7321457 84522114 71076570 17185000 27460052 37210369 4548934 6363387 52089287 53223156 63679890 76222034 86736534 22808061 73012052 66427914 54513370 18697065 68022745 45948017 47607405 28799210 35019397 49123137 94025537 2865811 79084137 80689999 85611819 8923179 86125019 8158509 55195465 18765947 35934872 63791460 95573325 62279697 10969681 12485463 33976946 79856963 77988836 61378348 41161745 12517371 63090879 98938634 20050648 8704780 52440124 32616796 55963477 36322107 69116950 2260988 40073566 13251866 19625186 91342886 63281244 20075150 59760769 29575091 36977720 22294986 96639487 23310664 9213800 58671778 21252477 75610776 44538458 22593504 86769629 97751929 41661452 66418836 15227464 19763026 79256843 78701431 43761852 72403989 47126349 94994446 9581739 57870439 80606075 7974319 67911812 67188257 18760886 91409119 33381047 8949764 68255286 4408916 15226324 24389730 89978466 91854740 56935344 33824057 44345729 27566429 21434582 65858429 24254123 38297000 39152536 32047972 76098284 74358554 86411798 81831242 43211770 36081023 58894025 18336420 92150196 28589664 52030941 84393602 14208708 37151108 68593816 45113497 11958429 36723743 31663215 17801783 82120763 73485314 27047048 11353950 67890104 79832033 17517375 22910147 82478057 43722668 51057032 86933932 61201452 37884766 49275814 16026808 91825810 96715758 36470791 47101357 14470161 71234489 95368573 77500474 88324084 55205191 420695 43835809 28205299 24838077 29359887 204563 76937138 83562588 46017133 14235635 49798215 51626556 51086809 40398617 614578 92653845 72740530 66726397 90783945 72495304 93846182 62860121 21418189 13396546 22905056 5634208 60542041 88284437 94254120 72056792 27092629 20661423 63096017 91784353 19065498 62988482 76817535 69541732 33461796 99433465 93131214 17165759 80012269 50243693 89317219 58115071 89761964 18985238 8207379 40123690 88649475 60480174 28556741 85604015 86619322 56722583 35095222 50136580 63842627 52679674 79598743 93417175 20558989 10528848 81876578 78586887 88780390 938066 83788694 61830456 55698074 42518169 60279138 22728902 85788289 93936818 45864088 36130399 7570867 4127622 61475994 32385012 71354553 16267107 88538733 54090724 20861809 77855996 26224129 39434509 49840634 68969250 95291415 12416610 67677562 21581515 44453740 7645435 79300414 24769059 92223861 94329536 86402566 92849467 32552095 53306654 23536868 84769917 77010767 24421852 64101962 85250183 75999101 65910152 20465759 70354821 31214482 19467979 68206324 46607077 81113714 24330066 95706519 16737188 97496326 29201804 96510824 50742131 89521902 95889936 88724254 11785317 87549829 22371241 66493413 33367276 29455727 69394107 95689862 57775150 86655463
样例输出
10546215 2562483 38460101 39543555 61692287 7325091 27679567 17176993 2265323 54351403 35433301 21771919 47427617 30551805 47306727 33100429 21602419 58089513 12484441 49002267 27667163 17867653 1759017 47647511 25836005 17810533 32281417 1126151 40290119 973435 3566511 13402131 58512455 7625729 2919857 60969753 704755 6849231 47175207 29896219 3436883 58120429 31126491 34660629 19943699 1142865 24030153 8135111 64053485 16136445 34066783 22387189 17747755 26328983 18059321 11598379 44599479 39513917 65920783 64814013 13245007 2522163 64068801 18695829 15689551 57561845 1859541 46091503 10572551 4905101 65254521 29717269 20296617 42957519 3676851 7302039 44007353 32302589 11460843 4390573 1434271 7589001 49783865 58420355 48951683 25709271 38382347 15226053 38115687 62231643 34649483 8035309 16606439 45170909 65924889 1473145 47452529 24506325 34951669 4641615 63018541 5940821 7653393 1644505 15190571 59151721 53809671 359187 52131861 27604229 11039467 31311551 10648973 50675999 17653661 14599045 22781289 32343403 42829061 48471101 15996933 21415015 27389327 7234483 1372875 1436909 57640207 43289613 66786945 57761633 44615001 17189169 32481235 53909297 31421717 30369051 34991225 45912299 9987557 13732591 39963225 32154713 7685457 36567121 13165235 8736129 65716239 14899403 14403551 64536389 16940395 6578945 16065225 16276991 21797959 44000151 25213127 13665761 21400563 10239475 14589549 5388743 2356345 62821025 11572861 39019147 876961 47330471 46037575 60433559 2740085 759999 39480093 3052307 4782837 65982445 13987293 13332695 27363319 64416921 10357335 7419931 26260015 20699415 1284783 38313969 11149985 56817193 28374079 204197 41330755 35331943 51566109 1196105 12578125 4118777 9248407 52304657 54261191 1266179 45134971 44829157 579741 51617143 16255831 46902767 25665941 1821375 9839759 62019875 32103421 2164485 65089453 47067303 5159673 15095213 18331597 14113501 8748845 29631555 17119465 40662883 23711575 20125143 4651785 6653387 3539649 21660581 64882641 45145459 36225607 43102253 19634887 2457505 55706249 57855011 58780403 18638027 6728399 22022939 13023387 37782727 10818185 6375637 31814217 28480165 7639997 37392837 235313 47137689 2063643 41211827 32409495 65311221 20644549 7021199 18866335 54999261 62721069 41125933 4692255 65679479 12972997 1569751 30442897 40707307 12625233 40295507 29580603 4302119 42741591 7551523 28967091 15358163 5711599 27385435 40410181 36481325 14112883 21759051 28099593 6349923 17222951 32505717 7885829 38829135 12812481 27613879 23595227 1048163 43456467 9960445 9349503 2610677 18879973 21886411 8819485 45670971 46885043 6956029 61034767 15655999 21884507 47573547 2117385 38918333 62798547 48673251 1306113 7259203 40349923 55184635 8898669 13977395 21906505 20702883 56841299 3825177 26731553 23115867 41910059 61940671 3025753 8722325 16265429 14595913 25444397 4839635 939693 24377171 50513759 54934865 22528901 54191941 19136315 56965595 9315853 39057741 9101009 18247327 65470885 58752143 8250155 12394663 7508085 57735955 20200071 2089815 8087255 5534817 10364597 5471765 45596809 49544683 17102717 33559691 14938389 3630671 8673807 451987 15212007 34624457 7737227 37251535 55133359 30429295 66821387 6252831 4576109 12200605 14993105 8514503 195371 7746469 22847465 8411923 33327103 14296059 26651403 5306005 1849043 4168949 10700509 89595 2393777 15775857 504171 55373981 1091895 51187253 33051447 3341137 39209807 54295157 12786575 45749209 47720367 29157487 2667529 2795359 4451941 14222451 37764431 14562657 5737517 54518803 483757 25083341 898505 966693 8689877 44431111 61320843 50707225 54021969 35321183 59699417 28954553 64295125 30954179 11603645 32483829 6214651 42227109 30976551 5576535 20040111 53857735 8259065 65197899 20345857 18434865 33840871 55285177 16091645 7337081 33528185 14105405 276203 668895 45291037 10539109 64672475 7353493 8565071 25646461 12273063 5714501 29787729 207265 1439991 52620537 109833 1584999 20977415 10597133 19918707 36318629 12548581 20642763 18864743 57491679 13394773 16667263 63015197 22586741 11276827 931659 52194499 17553325 65158227 58468267 57103215 63639371 20338839 11498227 21005357 17663623 35506083 32729535 12119793 433947 50710039 357213 7947807 921641 12483091 21593067 1539903 222697 4273755 82445 61952511 17305705 12688401 64144587 50389089 35206853 40324877 56925825 36082339 31507659 40158957 19774333 949317 46575101 19618333 26067227 3755571 1358461 24922993 913255 1409015 52609443 8172991 1733077 39043987 4640687 8858415 11892603 54035785 54227851 1844417 63412169 523547 40940967 40840873 11677077 6983187 49078885 59268815 1223179 1836979 6030989 16428955 62323153 23834759 15593589 5547875 44717089 27519341 4537893 3221399 7663279 61080673 13876531 35003463 91641 8169893 10247863 1249179 34795673 9212585 65162197 25992161 49493927 25629013 25787581 6937921 21494199 3460223 18078221 42499297 63432501 36743747 27339843 4153621 64619115 46380567 9107679 56175145 50235407 16464811 10477763 6380395 8383475 43505063 57899767 12729787 46313135 1926375 12674155 4461483 5587627 30919161 26314461 6310823 13213085 11397967 5811427 62141663 39635635 28154985 24030351 3377219 26904551 29995125 48961391 3550115 1561305 5993611 33645893 54176085 7294701 51292595 27039121 21441381 659157 6283167 43143671 20004099 19646161 54739099 50024247 1910595 36895165 14534997 27442481 471491 24729945 34142103 20054231 25590899 26574275 9492773 5008391 6410691 27197869 47947437 57245397 36092499 22681347 57835237 1115669 40302667 52257461 19664281 61059639 54432097 26963979 61107543 6421053 17780983 5289329 9901955 8000749 14836881 10126579 15925977 134439 42781759 1385817 52221503 66669107 27575059 10393637 8958055 19926411 1929145 26741093 13197805 14801853 20205379 743017 13620333 10667091 14110147 59454311 758369 36895331 31549047 65465339 14370417 43583415 41623817 4849245 26835373 3748393 48454039 54393369 16062011 8116859 58048751 2739503 17520511 5911577 39388997 19615643 582449 25798323 55022143 9122061 18683885 276043 56256341 35479513 25885853 13273155 33580501 47859275 11329319 41540727 18081477 37053909 20492527 49508703 4282855 3439189 32824225 47865287 48664769 41151435 10282721 26921811 21301893 26224565 50414411 15688053 54492661 8795685 35231707 62817031 4995147 9827305 48690559 16274409 1020927 4610183 59521569 47454625 12114921 64296727 56637183 17992879 13318783 19391513 64628061 192281 1828513 1996345 3525561 32182037 7815541 62808679 1976593 41590913 25537429 7302217 13118667 16309147 23904707 30314841 17686243 41944977 29502621 33590405 54823337 4348073 12944207 5054185 19531749 6780377 4299575 55020375 15344135 19829059 18136383 50384873 19457909 28323935 5200319 40542613 8139213 35929155 5264047 24531217 45242955 7520259 3409827 24580809 43947001 34497631 16283889 62560807 26562011 51882267 30392321 52864101 15945723 45534953 37447891 46656183 20360737 22478409 33619253 7842341 26536589 1824183 26667491 15013843 116295 2077935 29047113 44148193 21889179 13568211 51583395 14675805 27129595 3129693 3355341 665097 47458887 12614227 51706499 53691111 36912229 11714231 5039815 3915851 1048891 15460107 41847495 28320661 1322941 44369451 3026265 6170649 43871461 31193879 2357469