题目描述
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