QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#49650#2621. First OccurrenceMIT01#AC ✓97ms3852kbC++231.6kb2022-09-22 10:30:372022-09-22 10:30:39

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-22 10:30:39]
  • 评测
  • 测评结果:AC
  • 用时:97ms
  • 内存:3852kb
  • [2022-09-22 10:30:37]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
int cnt(ll x) {
    return __builtin_popcountll(x);
}
int main() {  
    int t;
    cin >> t;
    while (t--) {
        ll l, r;
        scanf("%lld%lld", &l, &r);
        ll len = r - l + 1;
        int pw = 0;
        while ((1ll << (pw + 1)) <= len) pw++;
        int at = max(pw - 4, 0);
        ll mx = 2e18;
        chkmin(mx, 1ll << (min(61, pw + 4)));
        ll cur = l & ((1ll << (at)) - 1);
        ll mt = (1ll << at);
        ll st = l / mt * mt;
        if (st < l) st += mt;
        auto chk = [&](ll x) {
            if (x == l) return 1;
            if (cnt(x) % 2 != cnt(l) % 2) return 0;
            assert(x < l);
            ll dif = l - x;
            ll cst = st;
            while (cst <= r) {
                if (cnt(cst) % 2 != cnt(cst - dif) % 2) return 0;
                cst += mt;
            }
            return 1;
        };
        while (cur <= mx) {
            if (chk(cur)) {
                printf("%lld\n", cur);
                break;
            }
            else cur += mt;
        }
    }  
    return 0;
}
/*
3
0 10
13 13
23 27
*/

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3792kb

input:

3
0 10
13 13
23 27

output:

0
1
5

result:

ok 3 number(s): "0 1 5"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3780kb

input:

316
5 16
2 21
11 19
9 14
2 7
1 4
10 18
9 20
7 15
5 21
11 12
16 19
2 23
8 15
13 20
4 14
10 21
18 22
16 22
11 21
19 22
4 12
7 9
9 15
14 23
14 24
8 12
11 22
6 19
16 23
7 21
7 24
8 8
9 11
3 3
4 8
2 3
5 13
13 18
9 19
3 15
2 14
17 23
9 9
18 23
4 6
2 13
2 17
15 24
20 21
3 20
6 10
8 21
8 16
12 17
2 2
7 22
0...

output:

5
2
11
9
2
1
10
9
7
5
2
4
2
8
13
4
10
10
8
11
11
4
1
9
14
14
8
11
6
8
7
7
1
5
0
4
2
5
1
9
3
2
9
0
10
4
2
2
15
0
3
6
8
8
0
1
7
0
0
2
9
1
2
13
0
0
0
3
0
13
8
11
0
4
5
2
4
12
12
1
9
7
14
0
1
0
8
11
0
13
9
10
1
3
3
11
0
12
8
1
5
1
0
1
2
3
1
5
11
3
2
0
6
2
8
6
6
1
0
0
3
2
13
0
0
8
11
10
0
6
1
10
0
5
4
0
...

result:

ok 316 numbers

Test #3:

score: 0
Accepted
time: 32ms
memory: 3672kb

input:

100000
192 214
289 344
64 222
37 307
290 325
392 444
8 142
201 347
130 144
192 420
69 220
425 445
19 441
133 275
93 342
222 435
135 375
0 76
65 114
130 347
67 160
143 293
154 278
281 368
135 334
100 256
57 267
276 309
283 329
75 296
152 271
163 199
277 289
14 338
242 343
337 385
157 209
61 93
98 247...

output:

0
161
64
37
50
8
8
201
34
192
69
41
19
133
93
222
135
0
65
130
67
143
154
153
135
100
57
84
155
75
152
51
29
14
242
113
157
61
98
188
16
160
106
54
65
60
176
96
5
69
24
17
85
66
257
30
43
140
58
21
344
58
166
136
72
12
69
53
44
248
42
37
227
16
198
80
85
15
57
68
1
24
91
129
222
54
20
51
81
39
18
14...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 24ms
memory: 3744kb

input:

100000
0 1
0 0
0 0
0 0
0 1
0 1
0 1
1 1
0 0
0 0
1 1
0 0
0 1
0 0
0 0
0 0
1 1
1 1
0 0
0 1
0 0
0 0
0 1
1 1
1 1
0 0
1 1
1 1
1 1
1 1
1 1
0 1
0 1
0 0
1 1
1 1
0 1
1 1
1 1
0 1
1 1
0 0
1 1
1 1
1 1
0 1
0 1
0 1
0 1
0 1
0 1
1 1
0 1
0 1
1 1
0 1
1 1
0 1
0 0
0 1
1 1
0 1
0 0
1 1
1 1
0 0
0 1
1 1
0 1
0 0
1 1
1 1
0 0
0...

output:

0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
1
0
1
1
1
1
1
0
0
0
1
1
0
1
1
0
1
0
1
1
1
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
0
0
1
1
0
1
0
1
0
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 24ms
memory: 3744kb

input:

100000
8 10
7 7
2 9
9 9
8 10
0 2
2 4
0 10
8 10
7 8
4 7
7 7
1 4
3 5
0 8
7 8
9 10
3 7
3 6
9 10
1 1
9 9
3 9
7 8
5 10
0 6
5 7
1 4
4 5
4 9
1 5
0 9
1 2
6 10
6 8
3 4
1 4
7 8
2 6
4 5
2 4
0 4
2 3
6 9
6 6
1 4
5 7
0 0
4 7
8 10
3 3
4 10
4 6
0 8
4 10
7 7
0 8
8 9
2 7
2 8
8 9
3 4
0 1
2 7
2 7
0 4
3 4
2 4
4 7
0 0
2 ...

output:

4
1
2
0
4
0
2
0
4
1
4
1
1
3
0
1
5
3
3
5
1
0
3
1
5
0
5
1
2
4
1
0
1
6
0
0
1
1
2
2
2
0
2
0
0
1
5
0
4
4
0
4
4
0
4
1
0
2
2
2
2
0
0
2
2
0
0
2
4
0
2
3
4
3
5
3
1
2
2
1
0
1
1
0
2
3
0
1
0
5
1
3
1
1
0
0
1
4
3
3
5
1
2
0
3
1
0
0
0
0
2
3
2
4
1
1
0
2
0
0
1
0
0
0
4
0
2
1
0
2
0
0
7
0
5
2
1
0
0
4
1
5
2
0
2
4
3
1
2
1
...

result:

ok 100000 numbers

Test #6:

score: 0
Accepted
time: 29ms
memory: 3676kb

input:

100000
40 96
67 91
3 46
3 28
73 95
16 32
49 58
46 85
14 21
6 70
7 47
70 90
53 89
13 82
54 88
1 56
18 95
75 83
28 40
28 64
5 88
44 69
11 28
67 78
10 55
77 89
7 69
21 28
15 22
5 41
61 73
23 62
44 96
68 87
15 64
15 44
33 69
3 17
2 53
28 82
26 36
0 17
28 84
67 68
72 92
57 74
8 87
32 93
26 61
40 64
61 74...

output:

40
35
3
3
41
16
1
46
14
6
7
38
53
13
54
1
18
15
28
28
5
44
11
19
10
45
7
21
15
5
13
23
44
36
15
15
33
3
2
28
2
0
28
2
40
9
8
32
26
40
13
5
30
48
56
18
36
15
3
3
8
2
6
16
11
11
3
41
4
3
3
20
12
12
2
17
4
71
8
2
31
0
1
19
6
39
46
40
3
34
58
1
34
22
12
24
15
11
15
2
44
36
52
55
30
47
29
18
16
61
6
3
35...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 30ms
memory: 3788kb

input:

100000
171 579
569 882
648 650
135 345
699 701
490 699
829 847
384 692
418 976
459 473
175 335
716 949
46 680
511 744
666 888
114 397
432 785
199 245
340 430
55 655
769 797
339 522
138 609
473 584
459 844
216 359
202 390
81 589
341 921
516 941
449 539
44 481
559 823
611 939
245 605
719 979
182 957
2...

output:

171
569
4
135
2
490
13
384
418
43
175
716
46
511
666
114
432
7
340
55
1
339
138
89
459
216
202
81
341
516
65
44
559
611
245
719
182
214
569
327
34
74
322
73
36
140
453
322
377
203
237
364
262
7
127
87
515
227
184
346
127
356
263
8
153
12
306
273
264
14
309
45
381
41
61
655
541
74
133
308
348
19
641
...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 42ms
memory: 3680kb

input:

100000
2704 9657
7144 9061
162 9802
3797 5720
6985 7642
2711 4932
3414 3885
5752 8572
6720 6907
771 9920
8924 9060
1130 3769
4073 9451
6519 9240
8668 8990
4485 7323
5627 6008
5509 5998
1750 3790
7220 8408
6730 6867
3816 5355
2995 7334
281 1557
3924 6577
2563 7991
5217 5340
1487 2908
3736 4449
3639 8...

output:

2704
1000
162
3797
841
2711
342
5752
320
771
220
1130
4073
375
1500
4485
507
389
1750
1076
330
3816
2995
281
3924
2563
97
1487
664
3639
2481
4793
2913
4242
2690
6101
2861
3308
87
697
592
952
55
1264
1906
4053
1978
2008
5193
103
83
735
903
1128
180
1265
3552
4776
3987
5062
2100
4007
4933
629
4326
281...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 35ms
memory: 3744kb

input:

100000
7987 72203
22455 32121
37909 77831
60850 62098
7183 53665
53721 95594
4169 75889
47722 60171
11286 57358
69359 74672
28037 75745
13193 14557
46589 51108
64053 99553
41499 93244
26190 86672
56660 57147
18430 76605
34835 63546
30844 72881
18396 71960
9120 87461
25193 32912
10653 88445
7862 5075...

output:

7987
22455
37909
2482
7183
53721
4169
47722
11286
20207
28037
905
9725
64053
41499
26190
1364
18430
34835
30844
18396
9120
617
10653
7862
2752
3141
4539
30047
10701
38076
676
29293
35100
44841
37623
5707
2502
25533
38274
13049
28511
20241
5315
1055
8656
64813
15462
59223
61024
18137
317
17996
6626
4...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 69ms
memory: 3708kb

input:

100000
252838 448281
363406 438885
373792 766014
263772 644963
189479 816498
219838 784594
132670 869941
621113 682853
685298 766477
661551 899451
394696 974847
337081 847724
4286 223464
183875 800582
535948 860170
33894 56469
205070 786430
5477 934010
634262 908598
669844 682391
82764 393100
483405...

output:

252838
68494
373792
263772
189479
219838
132670
129593
29938
661551
394696
337081
4286
183875
535948
33894
205070
5477
634262
14484
82764
90189
63752
250894
172973
593929
731691
114488
269585
150204
15170
324910
223090
767093
73660
236026
193063
250027
234914
38336
211774
209393
379949
38883
314968
...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 61ms
memory: 3672kb

input:

100000
7231601 8705808
6320580 6475087
4995381 5010929
22533 4632149
2513766 3386212
8433179 9507777
571423 4102573
5629917 6790532
5197372 6540847
3202056 9578326
6317614 7095587
7646818 9998035
6849931 7690527
4954654 8620995
125431 5042075
5497842 6704928
5777148 7883917
4977163 6087095
1834139 4...

output:

940145
29124
47413
22533
2513766
2141723
571423
1959901
5197372
3202056
26158
1355362
558475
4954654
125431
1827826
5777148
2880011
1834139
4621720
1947053
3969813
3863327
1063927
176866
67708
505937
4900922
104674
334240
866059
2269503
3863853
1362652
591152
66690
4464158
3936941
1642706
104742
702...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 53ms
memory: 3672kb

input:

100000
18728761 74621850
50174900 82750871
13295533 86607899
31942783 87444541
13044787 86172396
69608127 97088959
17039562 31541377
78706287 90746231
44119948 55247729
34060992 79016933
10885208 13447670
8888704 28480847
50365229 77712099
4366069 42403693
52953493 55085611
35571998 69062841
2523165...

output:

18728761
50174900
13295533
31942783
13044787
36053695
17039562
45151855
44119948
34060992
3545176
8888704
33581
4366069
2621845
35571998
2523165
3929630
33542685
527087
7215138
8486882
5253764
19614325
10219654
50790683
20016818
22408358
42232810
45749863
5240112
48445380
13181918
11272659
34291435
...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 41ms
memory: 3708kb

input:

100000
322430454 394144457
294764308 844972036
91188786 261279514
681223675 839591412
137594545 760685466
407757180 591969926
82317369 318959279
331114222 777074352
390080536 406957904
384252007 951313753
184833254 244408901
628919658 831597930
447872341 783416647
184439434 981423220
35181951 245986...

output:

188212726
294764308
91188786
211461627
137594545
5103996
82317369
331114222
29370392
384252007
184833254
628919658
447872341
184439434
35181951
96779021
212080000
32353012
314161296
77285266
34689251
65127588
9995295
43373084
11611898
439933409
313400931
568943497
1014231
91568586
114448614
23754567...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 44ms
memory: 3784kb

input:

100000
2865393365 5726056746
3366094907 9506951527
1857330233 4982210753
2876569341 4984144647
4584317515 5917241144
873968210 6138818150
1841224804 5940807284
6241232501 9944429743
3754232716 9933372390
1697853455 6286603941
1603911634 3111951259
1526894270 5637934164
8494645338 9071913796
10324874...

output:

2865393365
3366094907
1857330233
2876569341
2436833867
873968210
1841224804
6241232501
3754232716
1697853455
1603911634
1526894270
441581658
1032487468
6243626314
1354054991
2955227737
761751717
2162090118
1121365342
3661968077
388983589
1508138014
660257046
76611723
502361366
972796582
344828286
15...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 49ms
memory: 3736kb

input:

100000
70392589518 93960321819
59378670923 82250181191
24424390386 50591366208
30427996131 95041287490
6955472702 99628809605
54856214243 90930526944
77318118868 93865063580
41052505780 68408058242
39606905496 94747919521
51310857882 83273561662
63400251665 64521724998
75292712073 89904386304
492915...

output:

36032851150
7839063371
24424390386
30427996131
6955472702
54856214243
42958380500
41052505780
39606905496
51310857882
2196967697
40932973705
49291518793
30012783405
26942578
11568446178
10507887195
6584534384
5152850168
31191033798
35307204417
25312259702
39921610336
1453553456
20623926167
376950866...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 44ms
memory: 3748kb

input:

100000
691926730042 720152366408
321827857151 544075333880
3641714068 877421944592
498530792733 784391617206
130602863548 238782695900
778057166393 868287235398
140991280986 189561337274
72549796871 331326097968
163883587503 744871638152
424989547255 969553295297
423106380746 496110351671
2405684114...

output:

4731962682
321827857151
3641714068
498530792733
130602863548
159581875769
72271804250
72549796871
163883587503
424989547255
10789520330
34409981279
97435458966
83228639622
176273242795
20284059413
388114282308
217388650458
331453408412
9866800825
71641853192
30861971195
97908270831
48748056866
68652...

result:

ok 100000 numbers

Test #17:

score: 0
Accepted
time: 52ms
memory: 3676kb

input:

100000
5127480889764 9446413300343
1738056496543 5216131917932
465080941946 623914695464
2937575317052 9849336910784
881398909887 5727188976205
3356530648806 9609351903882
5356887959286 7310831929673
1595017497293 9837516037362
6180110056380 7605235213848
3216700799063 9891823124520
1713997237956 89...

output:

5127480889764
1738056496543
52764081530
2937575317052
881398909887
3356530648806
5356887959286
1595017497293
1232307731388
3216700799063
1713997237956
4866982122612
4827994847486
409706620513
332906598598
668124091151
127508054867
1072609498387
74741969956
2574142332994
3770862265181
2248444071261
3...

result:

ok 100000 numbers

Test #18:

score: 0
Accepted
time: 41ms
memory: 3704kb

input:

100000
53869313656108 66925456854959
51720827517265 77242606351478
85181575499163 97367633765370
18812950483618 68656285870145
29104556927396 30592510322058
53191999397573 76513323803378
68847849360005 82121390810096
10544064482670 24040356570003
55572098701197 66994390229934
16969241461059 37581973...

output:

1092755522860
51720827517265
49997203410331
18812950483618
2716277860772
415441264325
16071291226757
10544064482670
2795540567949
16969241461059
10361015047044
19985199835036
21184246165096
282147648971
30910783399653
40640201263095
7848991382573
7943517860488
1571079541702
51152153259237
2493211777...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 61ms
memory: 3760kb

input:

100000
494319164581032 941166372189105
40522112868595 132973511276637
543529623417152 770284324928967
644230853195905 771350619183228
366599543375933 704619614904641
111074818852981 254685024339507
455526734873146 456931401417730
158782256973266 705388626840173
267784813431099 681803918130705
216464...

output:

494319164581032
40522112868595
543529623417152
362755876485249
366599543375933
111074818852981
328920973882
158782256973266
267784813431099
216464971962375
515726942340397
122720224922615
63659442032518
619535045689573
224174156468132
72846286223838
354038022499407
56182832553676
131772162478545
327...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 66ms
memory: 3676kb

input:

100000
8333797901806446 9200686933856882
4924765806977134 9422087523870751
1142623307006420 5161411067159091
1687171507793177 6058779133089013
1133002689504086 7802707213509328
556256943021336 2985243217294017
5982558861910900 8865169126481750
7219102443053000 9363474502066735
3384930007030025 46011...

output:

1578398460750702
4924765806977134
1142623307006420
1687171507793177
1133002689504086
556256943021336
5982558861910900
463703001997256
7230286502153
3528053409700257
1276997514789909
5459401132037939
5787835402439348
1221679415233092
1155372474217001
2026669767819586
1046616249817942
5740342412472939...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 41ms
memory: 3744kb

input:

100000
15648963447429966 32202792948135656
7811817318381444 71156370018631740
5306745354234801 30948205884166692
12418367975093972 28110377135360201
341000394584205 88717975384791088
86501612772377972 98658836744149748
65280277062136511 94543231156392202
16428031099726527 49437016422064735
584005997...

output:

15648963447429966
7811817318381444
5306745354234801
12418367975093972
341000394584205
9940419107079540
65280277062136511
16428031099726527
4357404235206936
26425301229695457
22789220095957343
5282728381951866
45696477907053683
41822464236587599
30120600087981599
5028521233536503
40478001422495902
10...

result:

ok 100000 numbers

Test #22:

score: 0
Accepted
time: 68ms
memory: 3676kb

input:

100000
397005797438990781 528874840321747732
240125625187677673 281318259102295599
399454682528435833 424227077498264958
385965994819611425 486308168079795210
104591807178576429 913027433796870031
125742674385354594 346151510313168325
78908885043977578 557607817378232559
287423805775093671 479485229...

output:

397005797438990781
23952843073893865
39166712338796153
385965994819611425
104591807178576429
125742674385354594
78908885043977578
287423805775093671
6519021803500247
8175310153916857
34056210146475827
134475785818347152
202257646518318418
430048441516158326
621408236017996583
292947127948073364
3366...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 49ms
memory: 3620kb

input:

100000
520865256631708091 520865256631708092
221546117825951098 221546117825951099
631522846820923984 631522846820923985
404404552058754515 404404552058754516
901395466615272547 901395466615272547
262235784286171039 262235784286171039
418925320112852160 418925320112852160
626212153499819918 62621215...

output:

2
2
2
2
0
0
1
1
5
0
0
0
0
0
2
5
0
0
1
0
1
1
0
0
0
0
1
0
2
0
1
2
1
2
2
2
0
2
5
2
0
0
1
1
2
5
1
0
1
2
0
2
5
0
0
0
0
2
0
1
0
2
0
2
2
1
0
0
0
2
1
1
1
0
2
0
1
0
0
2
1
0
2
5
0
1
0
5
0
1
2
0
0
5
0
0
0
5
1
0
5
0
1
1
1
1
1
5
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
2
0
1
0
0
0
1
0
1
2
0
0
0
0
1
1
0
1
2
1
1
1
0
2
0
0
...

result:

ok 100000 numbers

Test #24:

score: 0
Accepted
time: 60ms
memory: 3748kb

input:

100000
866009293888766001 866009293888766010
264765313651980593 264765313651980597
292336070594689594 292336070594689595
326558565973164390 326558565973164398
495330697810294834 495330697810294843
968723973718025934 968723973718025937
475451602563234253 475451602563234261
759127295492996622 75912729...

output:

1
9
0
6
18
2
13
3
21
3
3
5
3
2
10
5
1
1
7
4
2
18
19
11
47
1
2
8
8
0
0
0
0
4
1
0
5
0
2
8
1
1
11
0
1
0
5
1
0
23
2
0
0
0
0
1
3
0
9
2
10
2
10
8
22
1
13
5
8
7
5
31
0
3
2
0
8
1
0
0
0
9
18
8
9
17
15
8
4
0
4
23
9
11
1
9
9
0
12
0
4
5
8
8
2
7
0
1
0
11
0
9
5
3
9
18
22
5
3
0
0
8
16
10
7
5
3
13
5
11
8
9
0
11
23
...

result:

ok 100000 numbers

Test #25:

score: 0
Accepted
time: 70ms
memory: 3832kb

input:

100000
736853650342636007 736853650342636056
22658472039617954 22658472039618032
141387850888113324 141387850888113359
819730244080025274 819730244080025318
577458192704662896 577458192704662911
128178699717073951 128178699717074037
501412896388799537 501412896388799627
465863788930898321 4658637889...

output:

71
34
60
186
0
159
305
17
146
121
26
55
191
13
182
142
176
247
180
83
182
6
6
37
95
103
18
47
174
19
147
30
105
22
128
15
57
16
42
55
166
1
119
115
155
84
179
10
11
55
7
133
37
33
168
36
11
164
86
52
148
46
32
161
94
1
1
75
0
39
148
152
0
11
188
134
97
54
162
43
18
30
19
177
4
35
183
11
99
379
39
31...

result:

ok 100000 numbers

Test #26:

score: 0
Accepted
time: 65ms
memory: 3832kb

input:

100000
607344588650387657 607344588650388361
664667572290183210 664667572290183540
748563648349234329 748563648349235086
148446435794159790 148446435794160243
903072627208377543 903072627208378490
254927347213737888 254927347213738127
548781106292734703 548781106292735226
582927270342797479 58292727...

output:

201
554
153
1198
1735
288
751
1191
745
997
74
400
253
82
146
3046
760
129
1513
1120
2364
1095
182
1534
582
1222
41
3056
1242
1362
171
198
2443
417
238
332
4
353
34
24
2319
2260
1882
915
595
1141
1880
1108
7
2833
1086
325
853
422
9
1418
311
880
413
125
474
240
5
2999
50
237
14
43
117
861
1224
244
639...

result:

ok 100000 numbers

Test #27:

score: 0
Accepted
time: 74ms
memory: 3756kb

input:

100000
222716346678755776 222716346678763725
893833481281478830 893833481281487016
456357852753601887 456357852753611781
284086466257709141 284086466257717698
227560138171451639 227560138171455109
941262964712938672 941262964712945112
595125072140725297 595125072140728202
66036548090602299 660365480...

output:

16832
12462
9567
18517
10487
7344
3121
827
1661
17328
12250
10311
2312
3697
1595
1352
3457
14330
7003
2669
2846
11659
3466
1551
1863
2732
6493
10444
3505
1288
922
2964
86
7354
16229
374
4951
1002
1543
2016
4399
4917
3639
8796
2134
2410
8372
4959
3351
19684
21048
4605
31847
102
15340
1553
4515
4561
2...

result:

ok 100000 numbers

Test #28:

score: 0
Accepted
time: 60ms
memory: 3784kb

input:

100000
798126597502481107 798126597502539777
919570699837706600 919570699837766225
590158886822139781 590158886822207419
417554692689956477 417554692689975416
281054483601741062 281054483601754829
186650755891459182 186650755891516907
231679996450604583 231679996450675243
303597734777646468 30359773...

output:

111315
69992
186245
36477
5382
128110
34343
191876
10681
50233
7954
141263
45686
65732
80331
30074
114919
147052
1581
158453
1800
13734
23649
149733
59158
185163
3245
313
181129
51282
12214
24086
102177
72215
144978
994
122059
12827
31127
44876
339903
192037
19166
20028
19328
110659
968
23253
82884
...

result:

ok 100000 numbers

Test #29:

score: 0
Accepted
time: 43ms
memory: 3748kb

input:

100000
946991721128194290 946991721128586406
864578612649463244 864578612649961425
420514396969826450 420514396969985815
341425132949844591 341425132950622976
580305337701905460 580305337702721175
997715898779422048 997715898779439572
268083313995345787 268083313995771655
972799298261674383 97279929...

output:

1372402
1510860
194706
1421935
2896948
19808
454523
715151
1529815
19442
291066
831516
2562391
332933
859802
5944
680523
1532478
3615
960564
383135
2863266
350618
1569964
1797769
281449
372550
337531
127590
1433227
123330
2953146
2924263
263748
161727
211653
174825
1433347
1784913
293424
973220
6936...

result:

ok 100000 numbers

Test #30:

score: 0
Accepted
time: 66ms
memory: 3676kb

input:

100000
97580163508442236 97580163518303995
558341718422317539 558341718423585007
234616352325091575 234616352328009225
864186478262991227 864186478269962807
151873135769557157 151873135779521625
646120207598873587 646120207603184326
797011185416221157 797011185419787651
497144278805261637 4971442788...

output:

758908
1567203
9814263
1030523
41425061
2223091
4141541
5123397
4081276
10166045
5946378
12183868
3423374
481810
5463822
1087268
57279
7429540
5466336
4838128
1698569
2483450
14976440
2407910
59038
10782067
10544052
6200535
468355
2440934
39478
471126
23597579
111639
31689
24678356
8597815
3022991
1...

result:

ok 100000 numbers

Test #31:

score: 0
Accepted
time: 74ms
memory: 3828kb

input:

100000
62327241999136556 62327242070067726
464034826113914843 464034826161633144
982451689010810022 982451689049705483
381135955037286947 381135955072978954
36171966838065349 36171966904195939
967882590283265968 967882590338882936
7282190166530518 7282190265775752
453494936898664839 4534949369551577...

output:

87045932
32380891
75025574
35680803
171296965
169768880
101718486
21526919
761299
94539435
47182548
60681318
92985224
31772416
58596300
44233239
33235248
132946220
259386182
21375014
124108915
161369039
612873
4502110
114861359
108221414
71439129
43797217
55146903
7486622
110003110
37835241
16298482...

result:

ok 100000 numbers

Test #32:

score: 0
Accepted
time: 65ms
memory: 3752kb

input:

100000
788528892822482282 788528893219166780
416830467634345244 416830467987410532
24227273319678281 24227274243482976
155331669186502404 155331670068631613
859290819959962505 859290820045590314
437627629786356275 437627630782903697
588826139790747348 588826139793652374
978976960937748515 9789769615...

output:

131132778
317175068
2753069385
70967044
41401225
3109018163
2172628
805070883
154998412
676944697
40926033
1809986420
240240536
106941145
2068964356
1533809119
522138639
1181539345
342665842
1234680951
1511714219
933294619
395414640
587687052
576864835
608940135
1204046840
71582655
152423439
2104527...

result:

ok 100000 numbers

Test #33:

score: 0
Accepted
time: 71ms
memory: 3792kb

input:

100000
522261935079009987 522261937369696680
805344196546093545 805344206296088658
82727717366872255 82727726908439253
649767352929812532 649767360095076047
971163092014099007 971163100073943732
947596003612197045 947596007643299967
220611948737109392 220611954401486829
954600857912942782 9546008645...

output:

2149035715
7064084969
11521439935
21508849716
12053932607
10500604085
95329680
9364775102
12457362228
569416323
10227513153
10607427922
2207921785
10593972075
11565289145
3694149234
19973463944
18900160482
9789729399
5221049771
2563011560
541854355
5064471357
4032269012
575787909
4366531712
18654013...

result:

ok 100000 numbers

Test #34:

score: 0
Accepted
time: 69ms
memory: 3852kb

input:

100000
969203101587829757 969203131987101604
255909932741679641 255909939408335993
421620881753529445 421620923193105019
424689969624450873 424690060888851441
173491826557845441 173491851611685362
148230536587279560 148230635234976892
119131297274924316 119131323809968760
10140633875276863 101406888...

output:

94377702397
1536154137
22662765669
29983180601
24250023873
13927611592
37039115548
9930990655
179356258090
25518634625
344654487
176103136253
84674622633
39663066412
95266613813
68800704076
8034929651
92050121691
23950664525
71121958676
5855340159
149092719247
170003010939
2273418885
372519380487
20...

result:

ok 100000 numbers

Test #35:

score: 0
Accepted
time: 71ms
memory: 3736kb

input:

100000
174612597457683293 174613554551803268
585508826567889362 585509510512231059
908765687595544417 908766101118846657
675809944260508986 675810315489052464
3087586186642706 3087899989314613
315727909099264225 315728826488296510
560351905044343526 560352711827213672
54492398262395380 5449325399908...

output:

1354873832285
1292591124946
635541008225
619806129466
707291661586
3145183385825
1197111093990
601989816820
920433585640
32670195819
25028955670
76801489792
812927408885
89559768612
406967410721
137777507233
781805445530
376515167221
1596260018309
559280871531
834551930741
325657645054
80211459835
5...

result:

ok 100000 numbers

Test #36:

score: 0
Accepted
time: 62ms
memory: 3760kb

input:

100000
798036734373089387 798040889605468586
705975164722640661 705984702191894187
86338711655073056 86340599024013566
367376755003409507 367383311788252378
603849731412114675 603849974641339457
887736784625887631 887745929563394320
801935282930002926 801941057220778010
182960066320696730 1829684752...

output:

2398840246379
18330946270997
5058642101536
16726023914595
144460791027
26280731634063
17472327855086
1331458770330
481419254018
25620375975608
26345596861135
24616579776224
9737788941269
11341674920019
2537913450286
9228424174103
263442160861
5427724668020
21748115738256
4421641276782
4500919325659
...

result:

ok 100000 numbers

Test #37:

score: 0
Accepted
time: 97ms
memory: 3832kb

input:

100000
42051910974943222 42066874213898010
993442542854452970 993493906985559506
456650243458527313 456746887029673301
987127240906246377 987156015120388883
90099174680772318 90159442042754474
109639114655646214 109675658394905503
878421744667072754 878450987593181181
515176680564821414 515245191121...

output:

6586328788982
82165670459114
97831233843281
47274140109033
27182133362398
74979971023366
8711097293042
77473184320934
83402856654624
20529561531054
122044638929349
54837282783241
133307461109126
106804673023574
83289605564220
21580757745411
57784252445303
42504434976875
204386797490512
5728212850854...

result:

ok 100000 numbers

Test #38:

score: 0
Accepted
time: 67ms
memory: 3756kb

input:

100000
442107085050919770 442417796939970412
75427249882640385 76063532955929518
454005801057747530 454108487702525031
233533581499076317 234460412581711251
68390040858971821 68448747235879511
429735594118423003 430708665979389972
202706480777913597 202897209150493635
952076738163192913 953062675708...

output:

191371615189850
1117856031027201
197769855992394
472300782653149
202727750815405
1893629518225883
44497546241277
1254266834596945
10917640634743
380692285710192
418868878878844
303799903917822
38042801081568
412909186835197
2229213509825424
1018949232794728
635354620509352
31867338734861
13415899049...

result:

ok 100000 numbers

Test #39:

score: 0
Accepted
time: 55ms
memory: 3744kb

input:

100000
805751006969126025 813251069984358831
386010080482641452 392606763631283824
621029176706564020 627522091122746679
218610755018746631 222390437330933654
954142057278645232 961955894920972943
964813279122651928 965493863673230845
319015865022013874 326576806231443820
671656884143687998 67506746...

output:

17621072179289225
25722110293001772
8539627384176564
2437972904962823
12889735158211568
3294758679051032
21778289615561138
620539665484094
11861873511807871
3421453594898111
6914788003174996
13242014840360834
1691611522423357
13062270459768504
2233180881200824
2043566554076004
24605281632151387
8168...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 71ms
memory: 3748kb

input:

100000
497565401626317716 590038009093351667
776590072838482850 855192538037455214
274752356883639534 351664210275368258
463179320540886557 489437326465912246
941363727759235805 966868681634887557
651240208424601070 655742286721889858
246439005329283520 307906688355586948
876026848259453662 94590603...

output:

65219837398750100
56014132459203490
58579574769855726
30833756313318941
40643802285136605
2721862083249646
30266223215499712
11335719804318430
88008577016639742
67415868948064770
51496737859087197
36067209528684003
87765273022586748
72598629471594330
5133445782554715
77746974506829248
46395061379132...

result:

ok 100000 numbers

Test #41:

score: 0
Accepted
time: 62ms
memory: 3744kb

input:

100000
267220279233973417 347982514757656473
350037824796500421 811833135043627428
603403805017750468 921508357632766297
323610367286888037 835332158333419951
607108207308130604 794583747238039284
516323694825904428 556568417010962400
194790650390724261 818223103373470552
313434762802706189 72335568...

output:

51047497120189609
350037824796500421
603403805017750468
323610367286888037
318877831156418860
83978130598336812
194790650390724261
313434762802706189
508357985210088273
445652401805403980
465820440401291246
9999419631730346
701025674425614248
550492182845665007
105012617345991664
22831653105566120
5...

result:

ok 100000 numbers

Test #42:

score: 0
Accepted
time: 45ms
memory: 3744kb

input:

100000
39591142752272 4785074604081161
2199023386624 35193096241152
134234144 269484032
134889984 288230376152793090
4503599627370496 4503599627374592
70368744177672 288234774198222848
558345748484 9904530128896
4352 144397212809429248
17213423616 274894946436
1048576 18760434974720
4194304 53687097...

output:

39591142752272
2199023386624
134234144
134889984
8192
70368744177672
558345748484
4352
17213423616
1048576
4194304
33554432
140746078289925
1099512152065
4096
8804720705664
262144
134217732
520
270337
70373106319360
58728456
36028799166447616
1134946157568
536870912
4311777284
68719476737
7476893817...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 80ms
memory: 3788kb

input:

100000
287104476110651383 504397660707352447
576451954028838783 576460752303423231
576179277292355583 576320014815068159
288230376147517439 576459652791664383
287103909309186015 540361586540281727
556194553980256255 576460752303407103
575334852396056575 576460717406814191
576460751129018367 57646075...

output:

287104476110651383
26386097504127
281474942353407
288230376147517439
287103909309186015
15762598695796735
1125899906318335
973078527
432336768134543287
432336699415068671
54043190696083455
70351530754046
1099377344511
274877906943
4503599073722367
4503598956281851
107944554056843261
4323455642275676...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

16290
0 0
0 1
0 1
0 1
0 2
0 2
0 3
0 4
0 5
0 7
0 8
0 10
0 15
0 16
0 21
0 31
0 32
0 42
0 63
0 64
0 85
0 127
0 128
0 170
0 255
0 256
0 341
0 511
0 512
0 682
0 1023
0 1024
0 1365
0 2047
0 2048
0 2730
0 4095
0 4096
0 5461
0 8191
0 8192
0 10922
0 16383
0 16384
0 21845
0 32767
0 32768
0 43690
0 65535
0 655...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 16290 numbers

Test #45:

score: 0
Accepted
time: 45ms
memory: 3620kb

input:

99681
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59
0 60...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99681 numbers