P20401 [HackerEarth] Raju and Manu are best friends. Manu loves mathematics. Raju keeps on querying Manu and Manu always solves his problem. One day Raju tries to trick Manu. He knows that his friend has a w
普及
题目描述

Raju and Manu are best friends. Manu loves mathematics. Raju keeps on querying Manu and Manu always solves his problem. One day Raju tries to trick Manu. He knows that his friend has a weak hand in base conversion. So he gives Manu an integer N and asks him to find the largest number from 0 to N (both inclusive) whose binary has maximum arithmetic sum of digits.
It seems our Manu got stuck and he has asked for your help. Help him help him to figure out that number.

INPUT

The first line of input contains an integer T denoting the number of test cases.
Each test case consist a single line containing an integer N.

OUTPUT

Output contains T lines, each line containing the solution to the respective test cases.

CONSTRAINTS
1 ≤ T ≤ 1000
1 ≤ N ≤ 100000

SAMPLE INPUT
1
4

SAMPLE OUTPUT
3

Explanation

Decimals from 0 to 4 can be represented in binary as {000, 001, 010, 011, 100}.Out of these ‘3’ has largest digit sum i.e. 0+1+1=2.

输入格式

见题面

输出格式

见题面

样例输入
1000 32193 50979 75511 31831 74903 55925 27630 20066 7412 48837 24545 71282 93621 60147 71674 25589 29104 55068 41691 35901 41461 19025 60558 2913 20760 70667 13499 75325 34416 76841 62412 16292 37167 10392 99106 42645 21300 61288 19782 2133 64854 84334 95367 65714 26289 42599 29553 76915 2908 84705 41834 18314 17338 76229 86362 26394 21440 90757 19098 10335 10256 54475 55511 7772 19956 29706 19022 41076 43192 17429 66382 21440 32904 56561 90358 84846 81305 98663 42394 33952 54658 40752 88287 2974 36386 6009 8502 58866 81210 72429 81377 1387 11180 62861 42251 27096 90833 26350 94496 77895 3205 60366 59414 3405 10977 46222 91176 28309 27800 95891 50217 30697 43669 37405 23951 5560 45190 98183 7174 8731 46687 80860 6195 50923 1325 64583 10544 38910 92754 6235 83954 41526 17264 60698 62430 91780 54046 86976 11306 23255 86857 57932 85527 78879 84253 45358 57763 23206 67511 9239 27545 35583 95478 80327 1215 60830 73785 88519 37318 46579 52228 56036 84950 1901 8591 44026 3607 70619 29765 13976 42258 24458 91768 41190 72632 46178 9091 96589 17133 90852 70789 95239 85326 84681 5819 95241 34590 45045 23363 19011 341 82908 55204 60476 99113 79302 86715 36352 93825 11256 603 37403 24754 39413 73286 36482 51962 59456 57616 14140 25390 62583 57640 69731 97327 46425 51192 96186 18656 67143 44325 10020 15033 25867 47944 44617 22081 38208 51471 34498 69722 44275 30968 41000 44919 78429 69879 95703 29382 32970 89391 66912 4219 17985 82369 86661 37033 40826 19963 10950 18628 2945 53154 24288 96283 39310 62907 41140 58449 6147 22008 1511 61769 56481 19338 5610 55475 29734 62985 83482 50508 21602 22488 49438 1109 93490 92469 48281 15167 26980 60007 60562 86284 28108 36306 97495 45265 38700 69621 82632 61707 17540 90788 87075 87331 12877 55393 57706 21932 59565 37263 53843 28 99078 96864 86679 41786 38721 95126 38059 85255 37537 48337 20327 18660 30725 22960 27425 61257 81832 50569 18870 99180 82550 2595 72920 68738 3634 2137 42934 93776 37272 65851 51865 26013 61192 62746 63802 7662 97842 48720 78591 74195 38180 85735 5861 41744 48924 82773 88120 78454 84555 2065 59109 41976 80931 58536 43236 76347 16062 3035 24639 667 85410 20616 40346 89236 54029 94004 80969 38271 15908 79335 14510 37820 12093 16377 84126 19162 33465 48638 69044 27788 61495 60131 39364 79918 80873 45045 80077 96611 31586 14135 7408 73623 54841 7413 51457 37490 27185 26534 33119 58715 70207 22258 20396 41469 69434 72467 9466 85875 35335 64432 39243 23739 91776 51381 14696 61493 82851 87889 83776 25145 47716 61201 85601 91217 24830 26331 63407 4901 11994 21633 14758 32100 26612 88484 33687 65549 81809 43861 84640 6863 18351 57773 36503 76159 9744 68892 76498 58789 88472 31167 18352 84791 25023 21839 16888 50765 28143 56956 2099 36247 24746 54384 49738 36983 20927 56222 12588 36106 41745 72699 46861 60827 96753 37776 81511 27080 20691 73092 94781 57441 94326 41322 81924 68686 59107 32630 20780 64519 1143 68618 67795 36271 94914 27025 46047 69810 65237 87395 18981 80386 47161 73033 78827 48869 97802 17800 17016 12539 41576 17631 85456 71567 10827 36135 2117 8330 77574 21255 2171 80858 58890 55648 86773 44004 18372 7341 75592 72356 79252 69147 26337 7406 10841 75456 44758 28193 49382 63211 71991 49386 66746 266 2621 83711 6067 38739 56474 66649 62007 63625 99868 30481 95239 97630 87986 32074 35624 92030 78985 84172 46655 80347 52626 13517 94909 96730 51433 70789 92591 64128 50786 47107 58663 38737 55848 9788 74661 56614 17868 56060 94936 66011 60129 97594 7933 44659 4725 31027 35019 95090 95327 20020 96454 83091 18224 12973 70298 34417 34222 47128 19344 33182 47298 44636 63623 71644 52466 89022 31595 85597 24908 81545 31816 72173 35194 16107 48709 27589 1281 78640 80980 61197 16995 72321 9325 39206 28827 93497 1226 86505 68121 34856 34970 28266 84122 72176 52479 84330 64843 98887 31072 38883 77352 8710 97996 95487 6826 90822 98385 93293 24596 94243 67223 4080 69424 38590 48962 51756 83358 96845 54664 96041 3791 52479 45806 293 76719 38011 86367 59758 22680 95050 10362 1030 56519 56854 10690 76074 34842 43624 66969 64912 80936 78029 94982 69905 15898 73879 18424 31544 6881 24377 34817 20755 28590 18060 71800 65947 22570 40322 7424 54390 30288 76312 58651 6964 70693 17036 25956 62932 30649 84674 18745 27110 37540 35375 76229 25649 87328 68224 41481 88618 8506 67617 42586 27692 52609 32906 84103 5438 15339 4009 54514 99064 8875 74549 10882 45978 25539 95140 10662 21061 55781 8601 22382 36332 49286 26154 61900 72482 37041 49079 68966 48771 64305 63826 60049 12842 19706 90264 67671 85255 84034 42502 3948 24877 63834 69656 66612 90742 19511 79944 39463 63596 45430 15692 26024 56051 10351 39059 95113 84147 20566 8760 10117 95049 25217 76563 59932 45764 43544 9009 8862 5922 57165 44580 35210 14060 77025 29482 33851 51304 64263 36183 16771 8930 56987 58082 57389 17028 30869 90908 89398 70334 416 56888 88932 34253 49961 1257 40076 39221 68623 92336 8030 74748 51904 86186 21678 75860 24063 74779 97916 54095 30055 22617 23729 62850 43571 10950 48870 2563 38592 50973 31910 65065 75878 97831 25507 88443 62945 95768 82919 43804 56316 11453 17127 3587 88248 67245 46344 47416 16600 69138 15274 45929 16172 35098 90184 25661 52570 68704 87628 58747 5550 90287 11661 40067 37793 33139 42392 11442 37178 35956 39960 67563 95908 14270 2302 31586 28178 73478 42541 19641 69613 33934 32394 23014 46324 74636 91658 24316 49170 66181 90693 29722 99714 55963 72736 43157 48342 88995 95937 30340 2177 96246 41238 20638 40624 59092 31490 72940 39816 63221 59664 88098 93686 88265 29590 84949 89062 40466 71322 69547 64897 24827 5061 17929 61649 70514 92518 61615 45836 68649 32634 11999 76880 55198 29800 84884 68670 73312 87020 89651 86589 79241 53891 28879 12299 13894 89874 13732 3189 48111 86969 37988 71145 23901 32791 69363 6184 56165 84914 10567 74495 29861 70473 54553 27555 26069 21177 8500 69267 37097 3206 89273 41390 85549 3910 99489 4111 45190 92797 77763 8166 72455 82986
样例输出
31743 49151 65535 31743 65535 49151 24575 16383 7167 32767 16383 65535 65535 57343 65535 24575 28671 49151 32767 32767 32767 16383 57343 2047 16383 65535 12287 65535 32767 65535 61439 16255 32767 8191 98303 32767 16383 57343 16383 2047 64511 65535 65535 65535 24575 32767 28671 65535 2047 65535 32767 16383 16383 65535 65535 24575 16383 65535 16383 8191 8191 49151 49151 7679 16383 28671 16383 32767 32767 16383 65535 16383 32767 49151 65535 65535 65535 98303 32767 32767 49151 32767 65535 2047 32767 4095 8191 57343 65535 65535 65535 1023 8191 61439 32767 24575 65535 24575 65535 65535 3071 57343 57343 3071 8191 32767 65535 24575 24575 65535 49151 28671 32767 32767 16383 4095 32767 65535 7167 8191 32767 65535 6143 49151 1023 64511 8191 32767 65535 6143 65535 32767 16383 57343 61439 65535 49151 65535 8191 16383 65535 57343 65535 65535 65535 32767 57343 16383 65535 8191 24575 32767 65535 65535 1023 57343 65535 65535 32767 32767 49151 49151 65535 1791 8191 32767 3583 65535 28671 12287 32767 16383 65535 32767 65535 32767 8191 65535 16383 65535 65535 65535 65535 65535 4095 65535 32767 32767 16383 16383 255 65535 49151 57343 98303 65535 65535 32767 65535 8191 511 32767 24575 32767 65535 32767 49151 57343 57343 12287 24575 61439 57343 65535 65535 32767 49151 65535 16383 65535 32767 8191 14335 24575 32767 32767 16383 32767 49151 32767 65535 32767 30719 32767 32767 65535 65535 65535 28671 32767 65535 65535 4095 16383 65535 65535 32767 32767 16383 8191 16383 2047 49151 16383 65535 32767 61439 32767 57343 6143 16383 1023 61439 49151 16383 4095 49151 28671 61439 65535 49151 16383 16383 49151 1023 65535 65535 32767 14335 24575 57343 57343 65535 24575 32767 65535 32767 32767 65535 65535 61439 16383 65535 65535 65535 12287 49151 57343 16383 57343 32767 49151 27 98303 65535 65535 32767 32767 65535 32767 65535 32767 32767 16383 16383 30719 16383 24575 57343 65535 49151 16383 98303 65535 2047 65535 65535 3583 2047 32767 65535 32767 65535 49151 24575 57343 61439 63487 7167 65535 32767 65535 65535 32767 65535 4095 32767 32767 65535 65535 65535 65535 2047 57343 32767 65535 57343 32767 65535 15871 2047 24575 511 65535 16383 32767 65535 49151 65535 65535 32767 15871 65535 14335 32767 8191 16375 65535 16383 32767 32767 65535 24575 61439 57343 32767 65535 65535 32767 65535 65535 30719 12287 7167 65535 49151 7167 49151 32767 24575 24575 32767 57343 65535 16383 16383 32767 65535 65535 8191 65535 32767 63487 32767 16383 65535 49151 14335 61439 65535 65535 65535 24575 32767 57343 65535 65535 24575 24575 61439 4095 8191 16383 14335 31743 24575 65535 32767 65535 65535 32767 65535 6143 16383 57343 32767 65535 8191 65535 65535 57343 65535 30719 16383 65535 24575 16383 16383 49151 24575 49151 2047 32767 24575 49151 49151 32767 16383 49151 12287 32767 32767 65535 32767 57343 65535 32767 65535 24575 16383 65535 65535 57343 65535 32767 65535 65535 57343 32511 16383 64511 1023 65535 65535 32767 65535 24575 32767 65535 65023 65535 16383 65535 32767 65535 65535 32767 65535 16383 16383 12287 32767 16383 65535 65535 8191 32767 2047 8191 65535 16383 2047 65535 57343 49151 65535 32767 16383 7167 65535 65535 65535 65535 24575 7167 8191 65535 32767 24575 49151 61439 65535 49151 65535 255 2047 65535 4095 32767 49151 65535 61439 63487 98303 28671 65535 65535 65535 31743 32767 65535 65535 65535 32767 65535 49151 12287 65535 65535 49151 65535 65535 63487 49151 32767 57343 32767 49151 8191 65535 49151 16383 49151 65535 65535 57343 65535 7679 32767 4095 30719 32767 65535 65535 16383 65535 65535 16383 12287 65535 32767 32767 32767 16383 32767 32767 32767 63487 65535 49151 65535 30719 65535 24575 65535 31743 65535 32767 15871 32767 24575 1023 65535 65535 57343 16383 65535 8191 32767 28671 65535 1023 65535 65535 32767 32767 24575 65535 65535 49151 65535 64511 98303 30719 32767 65535 8191 65535 65535 6143 65535 98303 65535 24575 65535 65535 4079 65535 32767 32767 49151 65535 65535 49151 65535 3583 49151 32767 255 65535 32767 65535 57343 16383 65535 8191 1023 49151 49151 8191 65535 32767 32767 65535 64511 65535 65535 65535 65535 15871 65535 16383 30719 6143 16383 32767 16383 24575 16383 65535 65535 16383 32767 7167 49151 28671 65535 57343 6143 65535 16383 24575 61439 28671 65535 16383 24575 32767 32767 65535 24575 65535 65535 32767 65535 8191 65535 32767 24575 49151 32767 65535 4095 14335 3967 49151 98303 8191 65535 8191 32767 24575 65535 8191 16383 49151 8191 16383 32767 49151 24575 61439 65535 32767 32767 65535 32767 63487 63487 57343 12287 16383 65535 65535 65535 65535 32767 3839 24575 63487 65535 65535 65535 16383 65535 32767 63487 32767 15359 24575 49151 8191 32767 65535 65535 16383 8191 8191 65535 24575 65535 57343 32767 32767 8191 8191 4095 49151 32767 32767 12287 65535 28671 32767 49151 63487 32767 16383 8191 49151 57343 57343 16383 30719 65535 65535 65535 383 49151 65535 32767 49151 1023 32767 32767 65535 65535 7935 65535 49151 65535 16383 65535 16383 65535 65535 49151 28671 16383 16383 61439 32767 8191 32767 2047 32767 49151 31743 65023 65535 65535 24575 65535 61439 65535 65535 32767 49151 8191 16383 3583 65535 65535 32767 32767 16383 65535 14335 32767 16127 32767 65535 24575 49151 65535 65535 57343 4095 65535 8191 32767 32767 32767 32767 8191 32767 32767 32767 65535 65535 12287 2047 30719 24575 65535 32767 16383 65535 32767 32255 16383 32767 65535 65535 16383 49151 65535 65535 28671 98303 49151 65535 32767 32767 65535 65535 28671 2047 65535 32767 16383 32767 57343 30719 65535 32767 61439 57343 65535 65535 65535 28671 65535 65535 32767 65535 65535 64511 24575 4095 16383 61439 65535 65535 61439 32767 65535 32511 8191 65535 49151 28671 65535 65535 65535 65535 65535 65535 65535 49151 28671 12287 12287 65535 12287 3071 32767 65535 32767 65535 16383 32767 65535 6143 49151 65535 8191 65535 28671 65535 49151 24575 24575 16383 8191 65535 32767 3071 65535 32767 65535 3839 98303 4095 32767 65535 65535 8159 65535 65535