QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344232#7181. Graph Cutsucup-team384AC ✓270ms162388kbC++202.3kb2024-03-03 19:49:212024-03-03 19:49:22

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3612kb

input:

4 5
1 2
1 3
1 4
2 3
2 4
10
+ 1
+ 2
?
?
?
?
?
- 2
?
?

output:

2
5
4
3
0
1
0

result:

ok q=10

Test #2:

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

input:

0 0
0

output:

result:

ok q=0

Test #3:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

0 0
1
?

output:

0

result:

ok q=1

Test #4:

score: 0
Accepted
time: 3ms
memory: 3700kb

input:

1000 2000
1 50
1 88
331 1
1 352
1 497
2 32
2 282
550 2
989 2
334 3
3 665
4 38
4 69
4 343
4 451
589 4
917 4
89 5
5 162
675 5
681 6
7 22
127 7
7 592
7 672
787 7
8 310
107 9
9 137
184 9
9 244
378 9
446 9
9 658
883 9
65 10
75 10
414 10
10 468
686 10
245 11
269 11
11 386
403 11
493 11
394 12
493 12
565 1...

output:

1
4
5
498
8
496
495
494
9
10
491
12
14
497
487
488
16
18
19
25
481
480
479
27
477
476
29
474
473
472
471
470
33
468
38
39
40
42
463
47
461
460
48
49
457
50
483
56
453
58
59
62
63
448
447
67
445
69
70
442
73
75
439
79
81
82
435
434
493
432
431
83
34
429
84
426
87
424
91
422
437
420
94
97
101
416
415
...

result:

ok q=100000

Test #5:

score: 0
Accepted
time: 27ms
memory: 6288kb

input:

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

output:

6

result:

ok q=100000

Test #6:

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

input:

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

output:

70
44
110
103
88
113
85
161
171
172
21
43
5
488
40
489
485
486
18
41
3
46
11
482
37
47
53
2
55
1
4
487
6
7
8
466
9
10
12
13
14
15
16
17
468
456
467
461
19
20
458
473
450
448
447
451
24
444
459
442
441
477
439
438
443
465
435
471
445
25
431
27
449
428
480
470
469
424
423
455
421
454
419
418
417
416
4...

result:

ok q=100000

Test #7:

score: 0
Accepted
time: 31ms
memory: 6228kb

input:

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

output:

180
25
1
498
497
496
495
494
493
492
491
490
489
488
487
486
13
484
483
23
481
480
479
478
477
476
475
474
473
8
471
485
470
468
482
499
34
37
40
54
57
61
68
26
458
72
62
77
466
21
7
20
465
453
469
450
467
445
443
449
451
472
439
448
457
33
464
434
433
463
462
461
429
45
460
59
35
459
454
440
456
42...

result:

ok q=100000

Test #8:

score: 0
Accepted
time: 28ms
memory: 6196kb

input:

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

output:

0
84
93
27
111
120
127
141
20
151
152
177
189
191
217
220
235
240
241
292
188
264
294
309
203
290
303
330
369
30
472
32
99
477
118
169
202
465
259
475
312
320
353
29
302
474
375
378
379
342
396
156
286
414
47
492
1
445
444
443
442
441
440
439
438
437
436
435
434
433
432
431
430
429
2
427
426
425
424...

result:

ok q=100000

Test #9:

score: 0
Accepted
time: 36ms
memory: 6180kb

input:

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

output:

0
0
0
0
0
0
0
0
81
102
379
526
547
364
378
809
823
824
970
138
184
191
583
629
288
322
636
393
733
991
281
726
767
838
416
95
540
861
984
1027
1073
1080
371
237
437
682
816
882
1126
166
308
43
101
131
211
111
301
339
404
488
1000
310
255
546
556
576
611
90
436
535
267
979
258
656
700
703
712
319
990...

result:

ok q=100000

Test #10:

score: 0
Accepted
time: 40ms
memory: 6212kb

input:

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

output:

0
0
0
0
173
618
1062
1505
1947
2388
2828
3267
439
884
1328
1771
2213
2654
48
493
189
634
937
1078
1380
1521
57
502
946
1389
1822
1831
1963
2263
2272
2404
2703
2712
2844
274
719
1163
1606
2048
2489
2929
3094
3142
3151
3283
3368
3533
3580
3589
3705
3721
3806
3971
4017
4026
4142
261
706
376
821
121
202...

result:

ok q=100000

Test #11:

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

input:

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

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 q=100000

Test #12:

score: 0
Accepted
time: 27ms
memory: 6288kb

input:

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

output:

2

result:

ok q=100000

Test #13:

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

input:

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

output:

5
9
10
498
497
11
495
12
15
16
17
490
20
488
487
21
23
25
31
33
35
1
2
478
479
477
475
474
3
4
471
500
469
6
8
499
496
468
463
473
461
466
459
458
457
494
455
454
462
453
493
450
13
14
492
446
491
489
443
442
18
486
439
438
472
437
485
484
24
432
452
430
429
428
427
426
425
7
423
456
464
444
440
19
...

result:

ok q=100000

Test #14:

score: 0
Accepted
time: 31ms
memory: 6292kb

input:

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

output:

5
10
11
12
497
14
17
494
493
492
20
490
489
23
487
486
485
484
483
27
481
30
22
31
477
476
475
32
36
29
474
472
488
495
16
468
465
38
39
462
461
25
459
470
457
40
455
41
42
43
44
450
45
47
48
49
445
444
443
50
52
440
58
62
437
436
435
63
66
432
67
430
429
70
427
426
71
424
423
76
421
456
419
418
442...

result:

ok q=100000

Test #15:

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

input:

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

output:

2
3
4
6
497
7
8
10
493
11
491
12
489
488
487
13
14
484
483
15
481
480
479
16
17
476
18
20
473
472
21
470
22
468
467
466
465
23
463
462
461
460
459
458
457
456
455
25
453
452
451
485
495
448
447
449
27
28
443
442
441
440
439
438
31
34
435
36
433
432
38
430
429
39
40
426
498
42
471
26
421
423
419
43
4...

result:

ok q=100000

Test #16:

score: 0
Accepted
time: 36ms
memory: 6288kb

input:

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

output:

1
500
499
3
497
6
495
7
493
11
12
15
489
16
19
20
485
23
26
482
27
480
29
30
32
476
33
34
473
36
38
470
469
39
467
466
41
42
463
13
474
462
459
481
43
45
455
454
453
46
47
450
449
49
447
51
445
53
57
442
60
61
62
438
63
436
68
434
69
432
431
430
70
76
427
78
80
81
82
422
83
84
419
87
88
416
415
24
4...

result:

ok q=100000

Test #17:

score: 0
Accepted
time: 37ms
memory: 6284kb

input:

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

output:

1
500
499
498
2
496
3
494
5
492
491
490
489
488
6
7
485
8
9
10
11
480
14
478
477
476
475
474
16
472
19
470
20
22
23
466
24
26
463
462
28
460
34
458
457
36
37
38
39
41
42
48
449
50
52
446
56
452
444
57
441
440
439
58
437
61
435
64
433
65
431
430
66
69
72
73
425
74
75
422
77
80
84
418
85
416
86
414
41...

result:

ok q=100000

Test #18:

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

input:

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

output:

6
500
7
498
497
8
9
494
10
11
13
490
14
488
16
486
485
484
483
482
481
17
19
21
22
476
475
23
473
24
25
470
469
468
467
466
28
464
30
462
461
31
459
458
36
456
455
454
453
452
451
37
38
39
40
446
41
444
443
43
441
440
45
49
52
53
435
434
55
432
57
430
60
61
427
66
67
424
68
69
421
420
419
418
70
71
...

result:

ok q=100000

Test #19:

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

input:

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

output:

1

result:

ok q=100000

Test #20:

score: 0
Accepted
time: 22ms
memory: 6196kb

input:

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

output:

16
24
34
38
1
496
495
494
493
492
491
490
500
499
487
486
485
10
498
482
22
18
480
478
477
476
475
474
473
472
489
6
469
483
467
12
465
479
463
4
466
20
21
471
457
484
455
26
28
497
451
39
449
40
41
44
8
444
488
453
43
42
439
5
450
445
435
3
433
13
431
458
31
432
35
426
436
424
423
422
17
462
32
418...

result:

ok q=100000

Test #21:

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

input:

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

output:

1
500
499
498
52
496
495
33
493
492
491
490
489
488
487
10
485
484
483
482
481
480
479
13
497
476
477
474
473
472
471
470
469
468
467
466
465
464
463
462
461
460
459
18
457
456
455
454
453
452
451
450
449
448
447
20
22
444
443
24
28
30
486
438
445
37
435
434
48
440
494
57
429
27
427
426
428
59
61
62...

result:

ok q=100000

Test #22:

score: 0
Accepted
time: 33ms
memory: 6280kb

input:

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

output:

0
0
81
144
221
35
278
375
241
164
27
194
220
239
305
264
118
66
303
308
345
351
360
480
376
401
418
425
140
440
472
246
93
94
191
228
6
174
235
269
127
309
321
89
336
366
72
162
311
358
199
274
451
361
7
65
452
42
102
124
487
390
399
408
410
417
22
467
48
493
161
198
37
215
222
120
223
70
69
209
9
4...

result:

ok q=100000

Test #23:

score: 0
Accepted
time: 40ms
memory: 6292kb

input:

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

output:

254
186
349
631
699
794
57
108
296
502
131
122
147
997
253
553
567
576
45
490
38
483
592
698
14
459
741
903
927
934
305
750
946
1011
1020
1036
1075
42
487
295
327
214
292
659
737
740
96
199
541
54
177
499
420
622
644
285
168
364
143
380
416
588
613
730
772
809
370
401
815
825
846
861
865
931
943
153...

result:

ok q=100000

Test #24:

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

input:

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

output:

0
0
0
0
342
787
1231
1674
2116
2557
162
607
1051
1494
202
647
1091
1534
1936
1976
2377
2417
2817
2857
2997
3256
3296
170
615
423
318
763
152
597
868
21
134
386
466
579
831
102
326
547
308
151
991
596
69
396
514
753
771
186
631
15
460
360
805
841
395
840
904
910
87
106
111
532
551
556
443
995
976
100...

result:

ok q=100000

Test #25:

score: 0
Accepted
time: 22ms
memory: 6228kb

input:

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

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 q=100000

Test #26:

score: 0
Accepted
time: 26ms
memory: 6232kb

input:

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

output:

1

result:

ok q=100000

Test #27:

score: 0
Accepted
time: 25ms
memory: 6184kb

input:

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

output:

242
78
207
4
12
27
29
35
40
54
14
22
23
19
494
11
485
3
49
72
17
480
26
1
477
476
483
10
484
496
490
15
469
468
479
487
465
21
463
489
461
497
460
471
458
24
25
454
453
452
451
450
478
28
447
486
467
444
30
492
441
42
464
43
6
455
7
434
433
448
431
456
430
475
427
426
425
474
423
422
459
420
473
472...

result:

ok q=100000

Test #28:

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

input:

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

output:

6
9
83
38
129
264
210
291
304
305
306
337
133
499
8
12
53
54
483
498
91
2
89
13
106
112
135
3
17
136
146
147
21
58
105
466
85
110
116
462
130
149
102
458
43
457
488
454
453
142
153
104
117
448
100
447
90
444
164
487
42
472
27
438
437
84
123
479
433
34
1
430
429
432
4
5
425
424
423
422
421
420
419
41...

result:

ok q=100000

Test #29:

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

input:

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

output:

383
829
413
859
1274
2
288
64
80
136
166
200
204
212
224
27
28
157
161
209
72
192
22
81
123
229
279
321
328
194
333
340
472
292
471
59
82
352
42
486
466
358
364
372
390
428
432
67
233
439
218
55
141
283
32
63
196
476
446
445
327
354
442
163
440
261
263
441
400
370
165
499
425
430
503
998
997
996
58
...

result:

ok q=100000

Test #30:

score: 0
Accepted
time: 28ms
memory: 6284kb

input:

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

output:

0
246
692
1137
1581
2023
253
699
1144
328
774
134
580
213
659
1025
1104
1219
408
118
564
348
76
522
77
161
523
607
794
207
653
854
191
369
637
815
967
968
399
845
119
81
527
364
565
104
130
418
424
428
550
576
810
864
126
10
215
239
456
79
154
423
286
31
477
133
525
572
579
600
270
661
685
972
716
9...

result:

ok q=100000

Test #31:

score: 0
Accepted
time: 39ms
memory: 6224kb

input:

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

output:

0
0
0
0
0
0
218
332
663
777
1108
1222
1552
1666
316
761
1206
1650
50
495
252
233
426
678
697
872
237
682
940
1123
1127
1142
1317
1384
1567
1571
1586
1995
1761
1827
2010
2014
12
39
63
180
427
457
484
508
625
873
902
929
953
1070
1318
1346
1373
1397
238
683
73
518
963
1128
1407
1514
1572
1762
1789
181...

result:

ok q=100000

Test #32:

score: 0
Accepted
time: 25ms
memory: 6276kb

input:

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

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 q=100000

Test #33:

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

input:

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

output:

5

result:

ok q=100000

Test #34:

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

input:

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

output:

3
10
13
498
15
496
16
1
2
4
491
5
6
488
487
7
485
484
8
9
12
14
493
478
486
476
494
474
17
472
500
477
470
482
20
466
21
23
463
469
461
460
459
492
468
456
490
454
453
452
451
450
449
448
489
446
445
475
443
455
442
440
441
438
437
444
435
439
467
432
431
499
429
428
427
480
425
424
423
422
421
436
...

result:

ok q=100000

Test #35:

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

input:

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

output:

4
500
499
7
497
496
495
14
15
18
20
22
489
24
5
486
485
484
483
482
487
480
25
26
477
27
31
34
473
498
471
470
472
468
36
37
38
464
39
40
461
13
459
460
43
49
51
52
453
53
451
54
56
57
60
61
445
62
16
493
442
462
47
438
9
436
469
434
433
491
19
430
432
429
23
6
17
21
423
422
12
458
421
467
417
465
4...

result:

ok q=100000

Test #36:

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

input:

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

output:

2
3
499
4
5
496
495
6
493
492
7
490
12
14
487
15
17
18
21
23
25
480
26
478
479
476
28
474
473
472
29
470
469
30
467
32
465
34
35
462
461
36
459
458
43
456
46
16
20
464
451
477
449
448
447
446
450
33
443
460
441
440
51
438
437
436
52
434
57
432
60
64
429
428
66
426
425
68
71
422
421
420
419
418
417
7...

result:

ok q=100000

Test #37:

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

input:

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

output:

3
4
499
5
497
496
7
494
493
492
9
490
12
13
487
14
15
17
489
482
481
480
479
491
478
20
475
21
473
472
23
26
469
27
467
466
29
33
463
34
461
460
459
458
35
36
455
41
453
43
451
450
449
44
447
446
445
45
46
442
441
47
48
438
50
436
495
49
433
432
435
430
429
434
427
428
51
53
423
56
58
420
419
60
417...

result:

ok q=100000

Test #38:

score: 0
Accepted
time: 37ms
memory: 6356kb

input:

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

output:

1
500
9
498
11
12
16
22
493
492
491
490
489
27
487
486
485
29
483
482
481
31
479
478
30
34
38
474
42
472
471
470
469
48
467
466
465
464
463
49
461
460
459
50
51
456
53
454
453
452
451
450
449
448
447
446
445
55
57
58
60
440
3
438
437
436
435
434
439
61
431
65
72
73
427
76
443
425
77
78
79
420
419
81...

result:

ok q=100000

Test #39:

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

input:

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

output:

1
500
4
5
8
496
11
12
15
492
16
490
17
488
487
19
485
20
25
26
481
27
28
478
477
29
30
33
34
36
37
470
469
468
467
38
40
464
43
45
47
460
459
48
49
456
455
51
453
452
52
53
449
448
56
446
58
444
443
442
441
59
439
60
437
62
435
434
64
432
66
67
429
428
69
426
71
424
423
72
421
73
75
78
417
416
415
8...

result:

ok q=100000

Test #40:

score: 0
Accepted
time: 26ms
memory: 6224kb

input:

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

output:

2

result:

ok q=100000

Test #41:

score: 0
Accepted
time: 31ms
memory: 6228kb

input:

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

output:

83
3
5
11
19
496
26
36
38
45
25
491
50
35
56
61
66
484
71
9
481
43
489
482
74
22
492
46
81
8
471
76
493
470
7
24
475
18
464
29
1
460
459
499
498
456
467
480
497
452
451
450
449
448
12
446
445
463
495
13
15
440
439
438
442
20
447
434
433
462
23
430
429
428
465
490
425
441
424
494
421
28
34
418
417
41...

result:

ok q=100000

Test #42:

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

input:

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

output:

0
32
19
55
99
108
59
162
167
206
6
70
82
102
116
190
208
248
141
118
258
286
288
294
114
25
27
131
176
8
166
471
80
101
473
224
106
465
127
150
194
231
52
498
207
211
239
240
126
21
452
38
154
467
180
454
244
445
168
444
442
233
440
484
270
189
436
273
221
433
210
431
223
142
121
428
4
2
472
9
422
1...

result:

ok q=100000

Test #43:

score: 0
Accepted
time: 28ms
memory: 6228kb

input:

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

output:

0
0
0
0
0
0
0
183
629
1073
374
820
314
351
760
239
258
14
274
460
138
584
685
704
797
84
101
328
396
431
530
102
547
2
184
308
372
343
87
333
377
426
439
448
993
148
169
533
197
990
989
51
497
354
398
988
357
205
154
75
59
115
117
133
196
261
104
1
455
454
453
452
451
450
449
474
484
446
494
470
462...

result:

ok q=100000

Test #44:

score: 0
Accepted
time: 34ms
memory: 6280kb

input:

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

output:

109
555
1000
1443
258
104
117
239
550
563
685
704
995
1008
1129
1148
114
158
184
560
10
168
325
456
614
630
771
178
224
345
90
427
187
122
381
221
190
351
447
536
356
568
624
124
362
389
20
342
466
1
469
468
467
470
465
464
463
462
461
460
459
458
457
489
455
454
453
452
451
450
449
448
477
492
26
7...

result:

ok q=100000

Test #45:

score: 0
Accepted
time: 37ms
memory: 6200kb

input:

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

output:

0
223
667
1112
1554
370
816
1261
1703
1997
2146
2439
2587
2878
3027
3318
140
583
96
174
197
539
418
617
640
864
984
1028
1062
1085
1309
1426
1470
425
871
1316
1504
1527
1751
1758
278
724
1169
1611
1869
1913
1947
1970
2054
2194
2201
2496
2311
2355
2389
2412
2635
436
882
1327
1769
2212
2642
2653
2751
...

result:

ok q=100000

Test #46:

score: 0
Accepted
time: 20ms
memory: 6272kb

input:

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

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 q=100000

Test #47:

score: 0
Accepted
time: 255ms
memory: 162252kb

input:

100000 100000
5722 1
35633 1
76503 1
2 8454
2 93428
3 91414
4 55025
21132 5
6 22400
6 80941
7 22043
7 29361
7 73158
78568 7
8 24159
8 26175
27612 9
39375 9
5454 10
24262 10
40601 10
11 8620
59525 11
11 79781
11 92891
64034 12
33728 14
14 59378
14 79826
560 16
16 31445
35262 16
17911 17
28509 17
9364...

output:

2

result:

ok q=100000

Test #48:

score: 0
Accepted
time: 241ms
memory: 162372kb

input:

100000 100000
32763 1
1 41318
52251 1
66464 2
83572 2
67186 5
7 64990
34545 8
8 96178
8628 9
10 8181
94794 15
16 33467
16 34451
85594 16
17 20413
31799 17
17 41753
18 61787
71853 18
19 5788
19 49136
97968 19
34661 20
20 61751
95244 20
20211 21
31082 21
22 96882
53538 23
53831 24
81268 24
25 52202
61...

output:

39777
48181
13198
22645
9533
1066
8174
12375
13512
13513
13514
12728
16155
17100
21764
21765
5804
13989
13990
19765
8756
19557
21766
12032
13252
4930
13522
189
1844
1845
8750
5176
5177
9930
15207
10158
5805
13628
1084
2924
4460
8664
12306
14893
15970
539
540
541
900
901
5293
8920
14147
15034
8609
21...

result:

ok q=100000

Test #49:

score: 0
Accepted
time: 202ms
memory: 162388kb

input:

100000 100000
98 1
1 39536
2 7197
2 36925
64304 2
3 90981
4 55694
4 58594
6 14112
6 61223
49657 7
49961 8
9 63064
84290 9
9616 10
10 26834
10 81424
11 28592
66665 11
11 67518
12 65671
12 77007
13 83518
88724 13
14 22525
28934 14
38904 15
18454 16
16 34371
33103 17
63576 17
46939 18
67514 18
18 72374...

output:

1993
3764
4708
7911
249
250
251
252
253
254
4316
4317
6849
10918
8018
8019
8020
12013
15688
15689
10169
15690
15691
10188
2538
4302
16065
16066
16067
5000
16068
17512
17940
20986
21537
3597
21789
12992
20396
20745
10520
12160
22718
14247
23223
23553
23847
6714
6715
15718
15719
2198
16596
23848
24130...

result:

ok q=100000

Test #50:

score: 0
Accepted
time: 184ms
memory: 162260kb

input:

100000 100000
1 30554
51310 1
1 71883
94585 1
2 40250
59351 2
2 60517
72989 3
4 3248
14035 4
4 90751
5 786
6 10125
87221 6
22862 7
7 57323
67940 7
40455 8
8 66854
9 34854
9 87440
43694 10
10 57462
82982 10
94968 10
47934 11
11 71829
24007 12
44565 12
48286 12
70260 12
12 70368
98761 12
20547 14
7549...

output:

11901
40431
49549
49550
49551
50261
26532
17118
45418
36518
35164
14555
3268
3269
3270
3271
14556
33488
8106
10949
9191
16879
18489
26073
31354
31355
34109
35452
18538
35453
35454
41209
41475
3678
48037
22737
22738
21390
29370
33367
33368
50164
25349
50660
52035
56894
14848
55161
13232
12467
16052
1...

result:

ok q=100000

Test #51:

score: 0
Accepted
time: 160ms
memory: 162300kb

input:

100000 100000
26140 1
46196 2
2 54845
78912 3
3 90871
4 12358
5 33609
5 43410
5 78393
47818 6
7 48862
13216 8
8 36636
8 40979
52931 8
8 80000
94821 8
52306 10
14072 12
36807 12
66342 12
344 13
13 4469
13 14570
13 52573
15 29037
15 38532
86576 15
16 9718
43023 16
16 86523
19 16448
20 15703
20 62471
8...

output:

0
0
0
0
33676
0
0
0
3296
56000
25081
25082
25083
38370
38371
6529
19895
19896
28482
38372
39238
1281
6360
12953
9074
9126
9127
9128
12954
12955
12956
43568
52444
8056
22544
23814
13771
28457
14145
34967
48282
61668
62237
62238
845
64094
11407
35692
40004
59096
67311
67816
68074
69480
70591
76367
811...

result:

ok q=100000

Test #52:

score: 0
Accepted
time: 100ms
memory: 162312kb

input:

100000 100000
2005 1
1 15170
57799 2
4 38977
4 57240
42542 5
5 53318
5 75678
6 88650
65147 7
8 53626
8 70633
22352 10
11 49862
12 14548
12 50661
12 69416
13 22675
13 57792
3230 14
61629 16
16 94304
19 4752
11292 19
19 23963
47970 19
3280 20
20 13431
37640 20
20 43437
22 59910
69629 22
94875 22
23 52...

output:

0
0
63811
63812
0
0
0
0
0
0
0
0
0
0
0
0
0
64070
0
0
0
0
0
0
0
0
0
0
0
0
0
17930
17931
0
0
0
0
0
0
0
0
0
0
22976
25298
25349
0
46890
63870
79011
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
23473
49655
54550
57471
74503
0
0
0
0
55883
79931
79932
0
0
0
0
0
0
0
0
94320
95578
95579
0
0
72970
93452
0
0
0
0
0
0
...

result:

ok q=100000

Test #53:

score: 0
Accepted
time: 31ms
memory: 162312kb

input:

100000 100000
40394 1
75982 2
3 18844
73366 3
88698 3
4020 6
6 73638
7 22013
65853 7
8 75952
8 91846
8 92431
35947 9
25852 10
60988 10
84698 10
49696 11
60792 11
94447 12
29797 13
14 32289
14 45866
85823 14
15 5953
19579 15
9976 16
16 26641
17 70399
80811 17
18 57277
19 24826
19 72978
15405 20
64474...

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 q=100000

Test #54:

score: 0
Accepted
time: 255ms
memory: 162372kb

input:

100000 100000
1 46719
1 85926
2 31507
3 10325
25701 3
4 20660
4 24390
5 28826
5 32895
5 65707
5 85849
26769 6
35848 6
8 31592
9 6175
10 10273
10 49762
8543 11
12 1257
12 49533
67310 12
12 85402
4042 13
13 91901
14 36759
95374 14
40235 16
16 95131
17 47185
49412 17
86267 17
30733 18
19 36525
99630 20...

output:

1

result:

ok q=100000

Test #55:

score: 0
Accepted
time: 259ms
memory: 162312kb

input:

100000 100000
1 14816
1 36843
1 67254
69974 1
3 22460
4 94861
51245 5
5 53683
54692 6
6 91387
6 91712
8 56288
8 88631
9 4475
23107 9
9 37340
18545 10
10 32507
10 37510
86500 10
57406 11
11 96238
486 12
12 44026
51175 13
14 92685
14 94886
14 99844
66818 15
58293 16
16 92531
17 32186
36963 18
18 53409...

output:

1
2
3
4
6
496
495
494
7
492
491
8
9
10
13
14
485
15
483
16
481
24
479
27
30
476
475
474
32
33
471
36
37
38
467
466
465
39
463
40
461
41
459
458
457
456
455
454
453
44
451
45
46
48
49
446
445
50
52
442
441
440
55
438
56
436
435
57
63
432
64
430
429
428
65
426
67
424
71
422
421
75
76
77
79
416
415
80
...

result:

ok q=100000

Test #56:

score: 0
Accepted
time: 224ms
memory: 162296kb

input:

100000 100000
1 92961
32241 2
2 81221
4608 3
16927 3
18769 3
3 43374
22317 4
55044 4
18810 5
6 72739
61007 7
9 25577
9 27864
34366 9
10 16913
30734 10
40980 10
60805 10
74697 10
82279 10
10021 11
23696 12
36468 12
51197 12
86124 12
12 89628
14 6535
14 21742
14 36158
57841 14
15 81216
15 84873
16 457...

output:

3
500
499
498
4
496
5
6
8
10
11
12
489
488
18
486
485
484
22
482
25
26
479
478
477
476
475
27
473
28
471
470
469
468
29
466
30
464
463
31
461
460
32
33
36
37
455
454
453
452
38
450
449
42
447
446
445
444
43
442
48
440
49
50
51
52
435
434
433
432
431
54
429
428
427
57
60
424
65
422
67
68
419
69
417
7...

result:

ok q=100000

Test #57:

score: 0
Accepted
time: 212ms
memory: 162312kb

input:

100000 100000
1 27333
1 84324
96084 1
9114 2
85952 2
3 5372
4 6733
9091 4
58622 4
4 86657
14441 5
55881 5
77265 5
5 80838
6 348
8 52617
8 61683
11583 9
9 73540
93581 9
94661 9
9 98721
46654 10
10 52226
12 55380
12 79729
13 40841
13 58505
80468 13
57058 14
14 59095
23508 15
68757 15
6286 17
17 39373
...

output:

1
2
5
6
9
11
12
13
493
492
491
490
16
488
17
486
485
20
21
482
22
23
479
24
477
25
26
474
28
472
471
30
32
33
34
37
40
464
41
44
45
46
459
458
457
456
48
454
49
54
451
450
55
57
65
69
70
71
72
442
73
74
439
75
437
436
435
434
78
79
431
83
84
87
88
426
425
424
89
422
92
420
93
418
94
96
101
414
102
4...

result:

ok q=100000

Test #58:

score: 0
Accepted
time: 198ms
memory: 162220kb

input:

100000 100000
60818 1
1 61357
77477 1
3 45025
59533 3
46950 4
78991 4
97104 4
36194 5
6 64485
1740 7
5623 8
23553 8
16292 9
62566 9
9 98158
10 23566
10 47129
84382 10
10 89508
11 12522
54918 11
82691 14
89591 14
15 22620
22939 16
56415 16
16 83923
18 29619
18 83502
19 24669
79130 19
43646 20
21 6966...

output:

3
500
8
498
497
10
13
14
493
15
18
21
23
488
24
486
25
26
27
482
30
480
479
32
34
476
475
36
37
38
39
40
469
43
44
466
47
464
463
462
461
48
49
50
55
56
57
454
453
452
58
450
449
59
60
446
445
62
65
66
441
67
439
438
68
436
435
70
72
432
431
73
74
428
427
426
76
424
78
422
82
87
419
88
417
90
91
94
...

result:

ok q=100000

Test #59:

score: 0
Accepted
time: 188ms
memory: 162272kb

input:

100000 100000
34616 1
58002 1
1 70045
10303 2
2 39631
40632 2
10056 3
41853 3
70173 3
4 92959
5 47483
16468 6
50684 6
67732 6
84535 7
47014 8
59046 9
10 65208
10 78362
11266 11
24545 11
12 21449
66415 12
92002 12
13 19643
13 23316
96267 14
91298 15
17801 16
49544 16
69757 16
4694 17
17 24548
221 18
...

output:

14
500
15
19
497
21
25
494
493
492
491
26
29
30
40
486
41
484
483
42
46
480
47
478
48
476
475
52
53
54
55
470
57
468
59
466
60
63
463
71
73
74
76
79
457
456
81
82
84
452
86
450
88
448
89
446
445
444
91
442
441
94
439
95
437
96
435
100
101
432
431
102
105
109
427
426
112
424
115
422
421
420
116
118
1...

result:

ok q=100000

Test #60:

score: 0
Accepted
time: 163ms
memory: 162236kb

input:

100000 100000
1 14279
25034 1
1 25644
1 33907
55554 1
32635 2
48898 2
67742 2
30821 3
62159 3
62878 4
4 99567
5427 5
81073 5
40389 6
68943 6
86783 6
7 7357
8 43901
8 49165
66447 8
15193 10
10 27651
52896 10
11 21927
31071 11
65058 11
1885 12
12 86604
13 34951
13 57211
73415 13
76672 13
31146 14
4934...

output:

1
500
3
498
497
496
495
5
493
9
491
10
489
488
16
17
20
22
24
25
481
26
479
27
32
33
36
474
37
472
471
40
42
468
44
466
465
464
45
46
47
460
48
458
457
456
50
454
52
452
451
56
449
57
447
446
445
61
443
442
441
63
439
64
67
436
68
69
433
432
70
71
72
428
73
75
76
424
79
80
82
420
419
86
417
88
89
41...

result:

ok q=100000

Test #61:

score: 0
Accepted
time: 262ms
memory: 162284kb

input:

100000 100000
36686 1
2 28317
3 43331
58975 3
9005 5
5 38587
85424 5
87253 5
91242 6
7 12636
7 28747
43112 7
56525 7
95056 7
8 67866
8 96414
15486 9
9 17569
9 27913
9 45216
57385 9
12037 10
10 26847
68194 10
10 69558
91082 10
1181 11
29864 11
11 51315
74564 11
11 99360
50347 12
12 70424
80616 12
810...

output:

result:

ok q=100000

Test #62:

score: 0
Accepted
time: 266ms
memory: 162224kb

input:

100000 100000
19575 1
26203 1
72508 1
1 97963
14667 2
16976 2
3 6175
3 67390
3 85817
3 95274
61098 4
5 63076
48837 6
6 85456
8 11139
8053 9
9 14304
9 42080
78302 9
87001 9
95714 9
10 11640
10 38250
11 68261
33284 12
34067 13
37576 13
13 83578
15 23823
35578 16
57809 16
17 35284
43161 17
17 47477
516...

output:

result:

ok q=100000

Test #63:

score: 0
Accepted
time: 270ms
memory: 162300kb

input:

100000 100000
36059 1
46485 1
23653 2
73424 2
2 74494
51828 3
4 33328
53661 4
34793 5
6 51871
55444 6
6 65656
8 16246
8 34477
10425 9
62445 9
21534 10
10 30313
60761 10
96061 10
7597 11
11 15469
63367 12
40382 13
14 75126
15 56288
15 84929
53927 16
64468 16
17 53139
18 5845
76176 18
19 24677
19 5891...

output:

result:

ok q=100000

Test #64:

score: 0
Accepted
time: 258ms
memory: 162252kb

input:

100000 100000
20177 2
2 98955
3 46743
3 46866
62628 3
12631 4
75181 4
5 54593
27546 6
6 31901
6 83336
6 90688
7 32220
7 63366
8 61776
37721 9
9 48206
9 70008
96585 9
10 62990
98079 10
11 11607
21944 11
11 80964
13 9208
13 49235
13 69968
13 85800
38176 14
57272 14
15 3765
16 67576
17 40546
17 44435
1...

output:

result:

ok q=100000

Test #65:

score: 0
Accepted
time: 264ms
memory: 162240kb

input:

100000 100000
1 33218
2 26924
4 22063
4 72727
83189 4
5 26165
50928 5
6 12110
17480 7
39161 7
7 76692
20436 8
36025 8
9 52297
9 58874
67940 9
10 17168
10 40179
10665 11
11 26766
11 26798
28558 11
41443 11
91932 11
11 96520
12 38384
89050 13
14 44040
14 60933
63286 14
14 91796
38298 15
83369 15
20977...

output:

result:

ok q=100000

Test #66:

score: 0
Accepted
time: 253ms
memory: 162352kb

input:

100000 100000
97038 1
2 12394
73478 2
27345 3
3 52828
3 94198
17649 4
34700 4
4 48092
90308 4
4 92571
5 73178
5 96066
1197 6
79796 6
6 95080
7 6897
7 96564
8 57604
8 70048
29738 10
10 42975
10 99064
11 20156
11 25952
51206 11
11 97949
38714 12
92965 12
10950 13
15 6617
8272 15
17383 15
37580 15
5035...

output:

result:

ok q=100000

Test #67:

score: 0
Accepted
time: 252ms
memory: 162208kb

input:

100000 100000
1 43054
1 66061
45045 4
81759 5
15827 6
6 40801
78430 6
6 83704
3488 9
32237 9
10 8261
10 37635
98555 10
82566 11
30294 12
68894 12
13 32989
92708 14
94972 14
15 41948
16 28327
20490 17
52712 17
18 23230
18 77251
9533 19
66382 19
20 10583
23214 22
32369 22
24 32167
75443 24
26 9052
278...

output:

result:

ok q=100000

Test #68:

score: 0
Accepted
time: 64ms
memory: 162352kb

input:

99970 100000
2 1
1 3
1 4
1 5
1 6
1 7
8 1
9 1
1 10
11 1
1 12
13 1
1 14
15 1
1 16
17 1
1 18
19 1
1 20
21 1
22 1
23 1
1 24
25 1
1 26
1 27
1 28
29 1
1 30
1 31
1 32
33 1
34 1
35 1
36 1
37 1
38 1
39 1
40 1
41 1
1 42
1 43
1 44
1 45
46 1
47 1
48 1
1 49
50 1
1 51
1 52
1 53
54 1
1 55
56 1
57 1
1 58
59 1
1 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 q=100000

Test #69:

score: 0
Accepted
time: 31ms
memory: 162220kb

input:

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

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 q=100000

Test #70:

score: 0
Accepted
time: 51ms
memory: 162280kb

input:

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

output:

1
0
500
0
499
0
498
0
497
0
496
0
495
0
494
0
493
0
492
0
491
0
490
0
489
0
488
0
487
0
486
0
485
0
484
0
483
0
482
0
481
0
480
0
479
0
478
0
477
0
476
0
475
0
474
0
473
0
472
0
471
0
470
0
469
0
468
0
467
0
466
0
465
0
464
0
463
0
462
0
461
0
460
0
459
0
458
0
457
0
456
0
455
0
454
0
453
0
452
0
45...

result:

ok q=100000

Test #71:

score: 0
Accepted
time: 39ms
memory: 162364kb

input:

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

output:

0
1
500
499
498
0
497
0
0
0
496
495
494
0
0
493
0
492
491
490
489
0
488
0
487
0
486
0
0
485
0
484
0
0
483
0
0
482
481
480
0
0
479
0
0
478
0
477
0
0
0
476
475
0
0
0
474
0
0
473
0
0
0
472
0
0
0
471
0
470
469
0
0
0
468
0
467
0
0
0
466
0
0
0
0
465
0
464
0
463
0
0
0
0
0
462
461
460
0
0
0
459
458
0
0
457
...

result:

ok q=100000

Test #72:

score: 0
Accepted
time: 31ms
memory: 162296kb

input:

99970 100000
2 1
1 3
5 1
7 1
9 1
1 11
13 1
15 1
1 17
1 19
1 21
1 23
1 25
27 1
1 29
31 1
1 33
1 35
37 1
1 39
1 41
1 43
45 1
47 1
1 49
51 1
1 53
55 1
57 1
59 1
1 61
63 1
65 1
1 67
69 1
71 1
73 1
75 1
77 1
79 1
81 1
1 83
85 1
1 87
1 89
91 1
1 93
1 95
1 97
99 1
1 101
1 103
1 105
107 1
109 1
111 1
1 113
...

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 q=100000

Test #73:

score: 0
Accepted
time: 89ms
memory: 162252kb

input:

99970 100000
2 1
3 1
5 1
7 1
1 9
1 11
1 13
15 1
1 17
19 1
21 1
23 1
1 25
27 1
29 1
1 31
33 1
1 35
37 1
1 39
1 41
1 43
45 1
47 1
1 49
1 51
53 1
1 55
1 57
59 1
61 1
63 1
65 1
67 1
69 1
1 71
73 1
1 75
1 77
79 1
1 81
1 83
85 1
1 87
89 1
91 1
1 93
1 95
97 1
99 1
1 101
103 1
1 105
1 107
1 109
1 111
113 1
...

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 q=100000

Test #74:

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

input:

99970 100000
2 1
3 1
5 1
7 1
9 1
11 1
1 13
1 15
1 17
19 1
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
37 1
39 1
1 41
1 43
1 45
47 1
1 49
51 1
1 53
55 1
57 1
59 1
1 61
63 1
1 65
1 67
1 69
1 71
73 1
75 1
77 1
1 79
1 81
1 83
1 85
1 87
89 1
91 1
93 1
1 95
1 97
1 99
101 1
103 1
1 105
1 107
1 109
111 1
1 113
...

output:

1
500
499
498
49986
0
50000
497
496
495
49999
0
494
0
493
492
49998
0
49997
0
491
490
49996
0
49995
489
49994
488
49993
487
486
485
484
483
49992
482
481
480
479
0
478
477
49991
476
49990
0
49989
475
49988
0
474
473
472
0
471
0
49987
0
50001
0
50500
470
469
468
467
466
50499
0
465
0
464
463
50498
0
...

result:

ok q=100000

Test #75:

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

input:

99970 100000
2 1
3 1
5 1
7 1
1 9
11 1
13 1
1 15
1 17
1 19
21 1
1 23
25 1
27 1
1 29
1 31
1 33
1 35
37 1
1 39
41 1
43 1
1 45
1 47
1 49
51 1
53 1
1 55
1 57
59 1
1 61
63 1
65 1
1 67
69 1
1 71
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
1 97
99 1
101 1
103 1
1 105
1 107
1 109
1 111
113 1
...

output:

0
0
0
1
49986
50000
49999
49998
49997
49996
0
500
0
0
49995
49994
499
498
0
0
0
0
0
0
497
496
495
494
493
492
491
49993
490
489
488
487
49992
49991
49990
49989
49988
0
49987
0
0
0
0
50001
0
486
485
484
483
50500
482
481
50499
50498
50497
480
479
478
477
476
475
474
473
472
0
0
471
470
469
468
50496
...

result:

ok q=100000

Test #76:

score: 0
Accepted
time: 99ms
memory: 162256kb

input:

99970 100000
1 2
3 1
4 1
1 7
1 10
1 13
16 1
19 1
1 22
25 1
1 28
1 31
34 1
1 37
40 1
1 43
1 46
1 49
52 1
1 55
1 58
61 1
64 1
1 67
70 1
73 1
76 1
1 79
82 1
1 85
88 1
1 91
1 94
97 1
100 1
1 103
106 1
109 1
112 1
115 1
118 1
1 121
124 1
1 127
130 1
1 133
1 136
139 1
1 142
1 145
1 148
1 151
1 154
1 157
1...

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 q=100000

Test #77:

score: 0
Accepted
time: 87ms
memory: 162280kb

input:

99970 100000
3 1
1 4
1 7
1 10
1 13
16 1
1 19
1 22
1 25
1 28
1 31
34 1
1 37
40 1
43 1
46 1
1 49
1 52
1 55
58 1
1 61
64 1
67 1
70 1
1 73
1 76
79 1
1 82
85 1
1 88
91 1
94 1
1 97
1 100
1 103
106 1
109 1
1 112
115 1
1 118
121 1
1 124
127 1
130 1
1 133
136 1
139 1
142 1
1 145
1 148
151 1
1 154
157 1
1 160...

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 q=100000

Test #78:

score: 0
Accepted
time: 51ms
memory: 162212kb

input:

99970 100000
3 1
1 4
1 7
1 10
1 13
16 1
19 1
22 1
25 1
1 28
1 31
1 34
1 37
1 40
1 43
46 1
49 1
1 52
55 1
1 58
1 61
1 64
67 1
70 1
1 73
76 1
1 79
1 82
1 85
88 1
1 91
94 1
97 1
100 1
1 103
1 106
1 109
1 112
1 115
118 1
121 1
1 124
127 1
130 1
1 133
1 136
139 1
142 1
145 1
148 1
1 151
154 1
1 157
1 160...

output:

1
0
33325
500
66648
0
33500
33499
33498
499
33497
498
33496
33495
33494
0
497
496
495
494
493
33493
492
33492
491
490
33491
489
33490
488
33489
487
486
485
484
483
482
33488
33487
481
33486
33485
480
479
478
477
33484
33483
476
475
474
473
67000
33482
66999
33481
66998
33480
33479
33478
472
471
470
...

result:

ok q=100000

Test #79:

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

input:

99970 100000
1 2
3 1
4 1
7 1
1 10
1 13
16 1
1 19
22 1
25 1
1 28
1 31
1 34
1 37
40 1
1 43
1 46
1 49
1 52
55 1
1 58
61 1
64 1
67 1
70 1
1 73
76 1
79 1
82 1
85 1
88 1
91 1
94 1
1 97
1 100
103 1
106 1
109 1
1 112
115 1
1 118
1 121
124 1
127 1
130 1
1 133
136 1
1 139
1 142
1 145
1 148
151 1
154 1
1 157
1...

output:

1
500
499
498
0
0
0
0
0
0
497
496
0
0
0
0
0
0
0
33326
495
494
493
492
491
490
489
33500
2
33499
33498
33497
488
486
485
484
483
482
481
480
479
478
33496
33495
33494
477
476
475
474
473
472
471
470
469
468
467
466
465
464
463
462
461
0
0
460
459
458
457
456
0
33493
0
66648
0
0
33492
33491
33490
3348...

result:

ok q=100000

Test #80:

score: 0
Accepted
time: 88ms
memory: 162312kb

input:

99970 100000
1 2
1 4
5 1
9 1
13 1
1 17
21 1
1 25
1 29
33 1
1 37
41 1
45 1
1 49
1 53
1 57
1 61
65 1
1 69
1 73
1 77
81 1
85 1
89 1
1 93
97 1
101 1
105 1
109 1
113 1
1 117
121 1
1 125
1 129
133 1
137 1
141 1
1 145
149 1
1 153
157 1
161 1
165 1
1 169
1 173
177 1
181 1
185 1
189 1
193 1
1 197
1 201
1 205...

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 q=100000

Test #81:

score: 0
Accepted
time: 134ms
memory: 162208kb

input:

99970 100000
1 2
1 4
5 1
9 1
13 1
17 1
21 1
1 25
1 29
1 33
37 1
1 41
1 45
1 49
53 1
1 57
1 61
1 65
1 69
73 1
77 1
81 1
1 85
89 1
93 1
97 1
101 1
105 1
1 109
1 113
1 117
121 1
1 125
129 1
133 1
137 1
141 1
145 1
1 149
1 153
1 157
1 161
1 165
169 1
173 1
177 1
181 1
185 1
1 189
1 193
1 197
201 1
1 205...

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 q=100000

Test #82:

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

input:

99970 100000
4 1
1 5
9 1
1 13
17 1
1 21
25 1
29 1
33 1
37 1
41 1
1 45
1 49
53 1
57 1
61 1
1 65
69 1
1 73
77 1
1 81
85 1
89 1
1 93
1 97
1 101
105 1
109 1
113 1
1 117
121 1
1 125
129 1
133 1
1 137
141 1
145 1
149 1
153 1
1 157
161 1
165 1
1 169
1 173
1 177
181 1
185 1
189 1
193 1
1 197
201 1
205 1
209...

output:

24994
1
500
25000
24995
0
49988
0
499
498
74979
0
497
496
495
0
494
493
492
491
490
50000
75000
0
49999
24999
49998
0
24997
24996
24998
25001
74999
0
489
488
487
486
485
484
483
49997
49996
49995
49994
0
49993
482
481
480
479
478
25500
25499
49992
477
476
25498
25497
475
474
473
472
471
470
469
468
...

result:

ok q=100000

Test #83:

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

input:

99970 100000
4 1
5 1
1 9
13 1
17 1
21 1
25 1
29 1
33 1
37 1
41 1
45 1
1 49
53 1
1 57
61 1
65 1
69 1
1 73
1 77
1 81
85 1
1 89
93 1
97 1
1 101
1 105
1 109
1 113
117 1
121 1
1 125
1 129
1 133
1 137
1 141
1 145
1 149
153 1
157 1
1 161
165 1
169 1
1 173
1 177
181 1
1 185
189 1
1 193
1 197
1 201
205 1
1 2...

output:

1
500
49987
24994
25000
74979
0
0
499
498
0
50000
49999
497
496
495
24999
24998
24997
24996
24995
49998
49997
494
493
492
491
490
489
488
487
486
25001
25500
25499
25498
25497
25496
25495
485
25494
25493
484
483
482
481
480
25492
25491
25490
25489
25488
25487
49996
49995
49994
479
478
49993
49992
47...

result:

ok q=100000

Test #84:

score: 0
Accepted
time: 94ms
memory: 162316kb

input:

99970 100000
1 2
4 1
6 1
11 1
1 16
21 1
26 1
31 1
36 1
1 41
46 1
1 51
56 1
61 1
66 1
1 71
1 76
81 1
86 1
1 91
96 1
101 1
106 1
111 1
1 116
121 1
126 1
1 131
136 1
1 141
1 146
1 151
1 156
1 161
1 166
171 1
176 1
181 1
186 1
1 191
1 196
1 201
206 1
211 1
216 1
221 1
226 1
1 231
1 236
241 1
246 1
251 1...

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 q=100000

Test #85:

score: 0
Accepted
time: 131ms
memory: 162280kb

input:

99970 100000
1 2
3 1
6 1
1 11
1 16
21 1
1 26
1 31
1 36
1 41
46 1
1 51
56 1
61 1
1 66
1 71
76 1
1 81
86 1
91 1
1 96
1 101
1 106
111 1
1 116
121 1
126 1
131 1
136 1
1 141
1 146
1 151
1 156
1 161
166 1
171 1
176 1
1 181
186 1
1 191
1 196
201 1
206 1
1 211
216 1
221 1
226 1
231 1
236 1
241 1
246 1
251 1...

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 q=100000

Test #86:

score: 0
Accepted
time: 63ms
memory: 162268kb

input:

99970 100000
3 1
4 1
5 1
1 6
11 1
1 16
1 21
1 26
1 31
36 1
1 41
46 1
1 51
1 56
1 61
66 1
1 71
1 76
81 1
1 86
91 1
96 1
1 101
106 1
111 1
1 116
121 1
126 1
131 1
136 1
141 1
146 1
151 1
1 156
1 161
166 1
1 171
1 176
181 1
186 1
191 1
1 196
201 1
206 1
1 211
216 1
221 1
226 1
231 1
236 1
1 241
246 1
2...

output:

2
1
39991
40000
59984
499
498
19997
497
496
495
494
493
492
60000
39999
59999
491
490
489
488
487
3
486
484
483
482
481
480
20000
19999
19998
479
478
79978
20001
80000
477
476
59998
475
474
473
39998
79999
39997
20500
20499
20498
39996
39995
472
471
470
469
0
468
467
466
465
464
463
462
461
460
5999...

result:

ok q=100000

Test #87:

score: 0
Accepted
time: 40ms
memory: 162308kb

input:

99970 100000
1 3
5 1
6 1
1 11
1 16
1 21
1 26
31 1
1 36
41 1
1 46
51 1
56 1
1 61
1 66
1 71
76 1
81 1
1 86
1 91
1 96
1 101
1 106
111 1
116 1
1 121
1 126
1 131
136 1
1 141
1 146
151 1
1 156
161 1
1 166
171 1
1 176
181 1
1 186
1 191
196 1
1 201
1 206
1 211
216 1
1 221
1 226
1 231
236 1
241 1
246 1
1 251...

output:

1
39990
0
19996
20000
19999
19998
19997
0
0
0
0
0
20001
500
499
498
497
496
495
494
493
492
491
490
489
488
2
20500
20499
20498
20497
20496
20495
20494
20493
0
20492
20491
20490
20489
487
485
20488
20487
20486
20485
20484
484
483
482
481
480
479
478
477
476
475
474
473
472
471
470
469
468
467
466
46...

result:

ok q=100000

Test #88:

score: 0
Accepted
time: 142ms
memory: 162256kb

input:

99970 100000
1 3
1 4
1 5
1 6
7 1
1 13
1 19
25 1
31 1
1 37
1 43
49 1
55 1
1 61
1 67
1 73
79 1
85 1
91 1
1 97
103 1
109 1
115 1
121 1
1 127
133 1
139 1
145 1
1 151
157 1
1 163
169 1
1 175
181 1
1 187
1 193
1 199
1 205
1 211
1 217
223 1
229 1
1 235
1 241
1 247
253 1
259 1
1 265
271 1
277 1
1 283
1 289
...

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 q=100000

Test #89:

score: 0
Accepted
time: 146ms
memory: 162276kb

input:

99970 100000
3 1
1 4
5 1
6 1
7 1
13 1
19 1
1 25
1 31
37 1
43 1
1 49
1 55
1 61
1 67
73 1
1 79
1 85
1 91
1 97
1 103
109 1
115 1
121 1
127 1
133 1
139 1
1 145
151 1
1 157
1 163
1 169
1 175
1 181
187 1
1 193
1 199
1 205
1 211
1 217
223 1
229 1
235 1
1 241
247 1
1 253
1 259
1 265
1 271
1 277
1 283
289 1
...

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 q=100000

Test #90:

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

input:

99970 100000
1 2
1 3
1 4
7 1
13 1
1 19
25 1
31 1
37 1
1 43
1 49
55 1
61 1
1 67
73 1
1 79
85 1
1 91
97 1
1 103
109 1
115 1
121 1
1 127
1 133
139 1
1 145
1 151
1 157
1 163
169 1
1 175
181 1
187 1
1 193
1 199
205 1
1 211
1 217
1 223
229 1
1 235
1 241
1 247
253 1
1 259
1 265
271 1
1 277
1 283
289 1
1 29...

output:

33327
49989
1
16665
2
33500
49990
3
66652
0
50000
49998
33499
33498
33497
17000
16999
16998
16997
16996
16995
500
497
496
495
16994
16993
494
493
33496
33495
49997
49996
0
83313
16992
16991
16990
83500
67000
66999
0
49995
49994
49993
49992
33494
16989
16988
33493
33492
492
491
490
16987
16986
16985
...

result:

ok q=100000

Test #91:

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

input:

99970 100000
3 1
6 1
1 7
13 1
19 1
25 1
1 31
1 37
1 43
1 49
55 1
61 1
67 1
1 73
1 79
1 85
1 91
97 1
103 1
109 1
1 115
121 1
127 1
133 1
139 1
145 1
151 1
157 1
163 1
169 1
175 1
181 1
187 1
193 1
199 1
205 1
1 211
217 1
223 1
229 1
1 235
1 241
247 1
1 253
259 1
265 1
271 1
277 1
1 283
1 289
295 1
1 ...

output:

16664
1
17000
16999
500
499
498
497
496
495
494
493
492
491
490
33328
33500
33499
33498
33497
489
488
487
486
485
484
483
482
481
480
479
478
477
476
475
474
473
472
471
470
16998
2
16665
16666
33329
49992
50000
49991
469
467
466
465
464
463
462
461
33496
460
459
458
457
456
455
454
453
452
451
450
...

result:

ok q=100000

Test #92:

score: 0
Accepted
time: 103ms
memory: 162312kb

input:

99970 100000
3 1
1 4
5 1
1 8
15 1
22 1
1 29
1 36
1 43
50 1
1 57
1 64
71 1
78 1
1 85
1 92
99 1
1 106
1 113
1 120
1 127
1 134
1 141
1 148
1 155
162 1
169 1
176 1
1 183
190 1
197 1
1 204
1 211
218 1
225 1
232 1
239 1
1 246
1 253
260 1
1 267
274 1
1 281
288 1
295 1
302 1
309 1
316 1
1 323
330 1
1 337
1 ...

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 q=100000

Test #93:

score: 0
Accepted
time: 111ms
memory: 162316kb

input:

99970 100000
1 3
1 5
6 1
7 1
1 8
15 1
22 1
29 1
36 1
1 43
50 1
57 1
64 1
1 71
1 78
1 85
92 1
1 99
106 1
113 1
1 120
127 1
134 1
141 1
148 1
155 1
1 162
169 1
176 1
1 183
190 1
197 1
204 1
211 1
1 218
1 225
232 1
239 1
246 1
1 253
1 260
267 1
274 1
1 281
1 288
1 295
1 302
1 309
316 1
323 1
1 330
337 ...

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 q=100000

Test #94:

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

input:

99970 100000
2 1
1 3
1 5
1 7
8 1
15 1
1 22
1 29
36 1
43 1
50 1
57 1
1 64
1 71
78 1
85 1
1 92
1 99
106 1
113 1
120 1
127 1
134 1
141 1
1 148
1 155
162 1
169 1
1 176
1 183
190 1
197 1
204 1
1 211
218 1
225 1
1 232
239 1
1 246
253 1
1 260
267 1
274 1
1 281
288 1
1 295
302 1
1 309
1 316
1 323
330 1
337 ...

output:

4
3
14288
2
1
497
496
14286
28572
14499
14498
495
494
28571
493
492
491
490
489
488
487
486
485
484
483
482
14287
14497
14495
14494
14493
14492
14491
14490
14489
14488
14487
14486
14485
42853
14484
14483
14482
14481
14480
14479
28570
481
480
42854
14478
14477
479
478
14476
14475
14474
14473
14472
14...

result:

ok q=100000

Test #95:

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

input:

99970 100000
2 1
3 1
4 1
1 6
7 1
8 1
1 15
1 22
29 1
1 36
1 43
50 1
1 57
1 64
71 1
78 1
1 85
1 92
1 99
106 1
113 1
1 120
1 127
1 134
141 1
1 148
155 1
1 162
1 169
176 1
1 183
1 190
197 1
1 204
1 211
218 1
1 225
1 232
239 1
246 1
253 1
1 260
267 1
1 274
281 1
1 288
1 295
1 302
1 309
1 316
323 1
330 1
...

output:

0
0
4
14288
5
2
3
28570
29000
28999
42853
57134
28998
28997
28996
28995
28994
28993
71415
71500
71499
71498
71497
71496
71495
14287
1
496
495
494
493
492
28992
28991
28990
28989
28988
28987
28986
28985
28984
28983
28982
28981
28980
28979
28978
28977
28976
28975
28974
28973
28972
28971
28970
28969
28...

result:

ok q=100000

Test #96:

score: 0
Accepted
time: 122ms
memory: 162252kb

input:

99970 100000
2 1
3 1
4 1
1 5
1 6
9 1
17 1
25 1
33 1
1 41
49 1
57 1
65 1
73 1
1 81
89 1
1 97
1 105
113 1
1 121
1 129
137 1
145 1
153 1
1 161
1 169
1 177
1 185
1 193
1 201
1 209
217 1
1 225
1 233
1 241
1 249
1 257
1 265
1 273
281 1
1 289
297 1
1 305
313 1
321 1
1 329
337 1
1 345
1 353
361 1
369 1
1 37...

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 q=100000

Test #97:

score: 0
Accepted
time: 149ms
memory: 162248kb

input:

99970 100000
1 2
1 4
1 5
1 6
1 9
1 17
25 1
33 1
41 1
1 49
57 1
1 65
1 73
81 1
89 1
97 1
1 105
113 1
1 121
129 1
137 1
145 1
1 153
161 1
169 1
1 177
185 1
193 1
1 201
209 1
217 1
1 225
1 233
1 241
249 1
257 1
1 265
273 1
281 1
289 1
297 1
305 1
1 313
321 1
329 1
337 1
345 1
353 1
1 361
369 1
377 1
1 ...

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 q=100000

Test #98:

score: 0
Accepted
time: 48ms
memory: 162200kb

input:

99970 100000
4 1
5 1
1 8
1 9
17 1
25 1
1 33
1 41
1 49
57 1
65 1
1 73
1 81
1 89
97 1
105 1
1 113
1 121
1 129
137 1
145 1
1 153
1 161
169 1
177 1
185 1
1 193
1 201
1 209
217 1
1 225
1 233
241 1
1 249
1 257
265 1
1 273
1 281
289 1
297 1
305 1
1 313
1 321
329 1
337 1
345 1
1 353
1 361
1 369
377 1
1 385
...

output:

1
12500
12501
13000
500
499
498
497
2
12502
12504
37498
12503
25001
49996
49995
496
494
493
492
491
490
489
488
487
486
485
484
483
482
481
480
479
478
477
476
12999
12995
12994
475
474
473
472
471
470
469
25500
468
467
466
465
464
463
462
461
460
459
458
457
456
455
12993
12992
12991
74987
3
12990
...

result:

ok q=100000

Test #99:

score: 0
Accepted
time: 40ms
memory: 162180kb

input:

99970 100000
6 1
9 1
1 17
1 25
1 33
41 1
1 49
1 57
1 65
73 1
1 81
89 1
97 1
1 105
113 1
1 121
129 1
137 1
1 145
1 153
1 161
169 1
1 177
1 185
1 193
201 1
209 1
217 1
1 225
1 233
1 241
249 1
257 1
265 1
1 273
281 1
1 289
1 297
1 305
313 1
321 1
1 329
337 1
345 1
353 1
361 1
369 1
1 377
1 385
393 1
1 ...

output:

0
0
0
12500
37496
12502
49993
50000
12498
1
12499
13000
12999
12998
12501
25000
62490
500
499
62500
62499
62489
62497
62496
62495
62494
62493
12503
37497
74987
37500
498
497
496
495
494
493
492
491
490
489
488
487
486
485
484
483
482
37498
37499
37501
38000
37999
37998
37997
25001
25500
25499
12996
...

result:

ok q=100000

Test #100:

score: 0
Accepted
time: 98ms
memory: 21388kb

input:

10000 100000
62 1
1 552
818 1
1 1204
1993 1
1 4007
1 4095
5262 1
1 5367
5784 1
1 6036
6091 1
1 6559
8108 1
1 8154
1 9191
9482 1
41 2
2 294
1572 2
1852 2
2 1895
3322 2
4360 2
4905 2
2 5027
5934 2
6198 2
6504 2
2 6870
8364 2
722 3
812 3
1347 3
1856 3
1990 3
2008 3
2578 3
3 3019
3 3248
3 3495
3 3616
3 ...

output:

2

result:

ok q=100000

Test #101:

score: 0
Accepted
time: 93ms
memory: 21272kb

input:

10000 100000
1 278
1 1411
1906 1
2107 1
2178 1
1 2299
2526 1
1 2856
1 3613
3796 1
1 4128
1 4196
1 4250
1 4631
5135 1
5224 1
1 5279
6206 1
1 6985
1 7310
1 7357
7722 1
7815 1
1 8282
9362 1
9571 1
1 9782
1 9999
874 2
2 1055
1187 2
2010 2
2 2173
2250 2
2511 2
2699 2
2756 2
2876 2
2 3802
4047 2
4937 2
2 ...

output:

3248
242
2307
72
241
995
199
123
259
928
1040
1130
59
1434
1701
427
323
214
605
610
2
1025
1762
1871
724
725
726
727
728
729
182
730
731
732
733
734
319
735
67
216
105
350
702
561
736
737
738
739
740
741
801
138
643
1023
256
263
705
104
706
707
426
460
708
510
688
689
248
690
584
437
969
691
692
693...

result:

ok q=100000

Test #102:

score: 0
Accepted
time: 88ms
memory: 21372kb

input:

10000 100000
1 257
1 1150
1 2495
4714 1
5052 1
5128 1
5130 1
1 5235
1 6273
1 7279
7296 1
1 7899
8429 1
8895 1
9133 1
1 9402
2 378
2 434
1060 2
2991 2
5009 2
5316 2
2 5857
2 5984
2 6490
2 6494
6963 2
2 7560
2 7816
7996 2
8202 2
2 8218
2 9608
893 3
3 1127
3 1318
1863 3
3136 3
3 3927
4162 3
4273 3
3 49...

output:

0
7465
1614
251
1910
679
2242
1693
2359
2455
681
682
683
684
539
685
686
687
688
689
690
691
692
693
966
1369
1960
2401
1997
2324
456
2402
1224
694
1260
49
2403
2404
1581
2405
1809
2406
2407
2408
2409
1210
2251
2410
2411
472
249
1066
1374
1625
886
1837
2322
2388
379
972
1383
112
184
1031
2165
1100
2...

result:

ok q=100000

Test #103:

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

input:

10000 100000
1 32
366 1
1164 1
1 1881
2317 1
2931 1
1 2932
3853 1
4011 1
1 4090
1 5006
5656 1
5696 1
1 6055
6674 1
7367 1
7599 1
8265 1
2 1468
2 1486
1670 2
2375 2
2 2729
3116 2
2 3202
2 3560
2 4047
2 4643
2 4645
4794 2
4958 2
5887 2
5947 2
2 6549
2 6992
2 7179
7436 2
2 7513
2 8130
2 8703
2 9686
514...

output:

0
15116
17567
17657
11119
13910
5148
12807
1807
4
4181
5396
5397
2369
299
548
4648
5398
5399
5400
5401
5402
5403
5404
5405
494
1182
1471
5406
5407
5408
5409
5410
5101
5411
5412
5413
5414
5415
1785
5416
3900
3883
5438
5639
5703
6151
402
3675
1946
3804
568
783
4340
4363
4526
4999
4998
4997
4996
4995
4...

result:

ok q=100000

Test #104:

score: 0
Accepted
time: 73ms
memory: 21392kb

input:

10000 100000
1 1173
1 2045
1 2146
1 2314
2389 1
1 2586
1 2796
1 3622
3650 1
1 3692
1 3985
4433 1
4520 1
5493 1
1 5514
6563 1
7220 1
1 7472
1 8043
1 8385
8565 1
9622 1
1 9735
2 97
2 131
167 2
1663 2
3416 2
2 4187
2 4386
2 4447
2 5022
5025 2
5179 2
2 5885
2 6919
8335 2
8400 2
2 8671
8807 2
9147 2
3 83...

output:

0
0
0
0
8931
18034
3368
3646
6002
5064
7532
3102
1223
423
3857
4792
5281
606
1525
2127
5489
910
1112
2662
2741
4591
5484
3296
5701
5902
1152
6095
6456
6598
651
737
1379
2695
2918
3573
4811
6904
7406
7766
7953
2529
2235
2871
4448
5761
6638
2258
3257
3810
4257
4525
4530
5305
5411
8546
8697
8858
9017
9...

result:

ok q=100000

Test #105:

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

input:

10000 100000
1 380
1 873
1 1618
1838 1
1 2767
3506 1
1 4453
4602 1
4754 1
4880 1
1 5778
1 5811
1 6230
7868 1
1 7911
8126 1
1 8233
9049 1
9356 1
2 10
2 537
658 2
2 1129
1461 2
2 2035
2237 2
3097 2
3513 2
2 3524
2 3931
2 4956
5072 2
2 5204
2 5302
2 5454
2 5562
5607 2
5774 2
2 5909
6017 2
2 6193
6622 2...

output:

0
27150
30684
36735
38811
39253
49145
64431
12441
15385
18770
21325
23949
24041
5091
15944
35025
41047
41532
41975
52191
54021
6692
18808
30169
32734
55281
55524
55535
55733
783
2886
9527
9528
9529
9530
9531
9532
9533
621
4684
4910
7271
8808
9534
4590
5105
6046
9535
9536
9537
9538
9539
9540
9541
954...

result:

ok q=100000

Test #106:

score: 0
Accepted
time: 23ms
memory: 21336kb

input:

10000 100000
1 223
924 1
1010 1
1 2164
1 2599
3130 1
3294 1
1 3555
1 3759
4080 1
1 4841
4948 1
1 5358
1 6539
7363 1
1 7747
9377 1
1 9393
1 9596
1 9941
376 2
2 623
878 2
1665 2
1759 2
2 1941
2135 2
3573 2
3685 2
3843 2
2 4021
5156 2
2 6157
2 6758
6934 2
2 7220
2 7354
7620 2
2 7815
2 8287
2 8564
8772 ...

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 q=100000

Test #107:

score: 0
Accepted
time: 109ms
memory: 21376kb

input:

10000 100000
1 246
483 1
1 766
1 1389
1 1977
1 2314
2563 1
2637 1
2826 1
1 4125
4414 1
4737 1
1 5172
1 5460
1 5727
1 6441
1 6611
1 6654
1 7016
7208 1
1 7265
1 7459
7666 1
1 7680
1 7784
8265 1
8518 1
9031 1
2 1115
2 1194
2 1496
1533 2
2 1578
1655 2
2455 2
2 2537
2785 2
2 3661
2 5953
2 6095
2 6250
728...

output:

1

result:

ok q=100000

Test #108:

score: 0
Accepted
time: 102ms
memory: 21280kb

input:

10000 100000
1 4
1 262
480 1
1661 1
1942 1
3141 1
3242 1
1 4520
5039 1
5322 1
5617 1
5702 1
6596 1
7549 1
8091 1
1 8150
1 8300
8880 1
8976 1
9057 1
1 9615
2 361
986 2
2 1260
1571 2
1831 2
2903 2
2 3659
2 4398
4775 2
4780 2
2 5425
6353 2
2 6520
2 7157
2 7742
2 8973
9025 2
50 3
3 677
3 816
924 3
1742 ...

output:

1
500
4
498
11
13
495
494
14
16
18
19
489
21
23
25
485
484
483
482
27
28
31
478
477
476
475
34
473
472
39
46
47
49
51
52
53
54
463
462
56
57
459
458
457
58
455
454
59
452
60
450
61
62
63
446
445
74
75
442
441
76
77
79
437
80
435
83
464
433
431
430
429
428
427
85
425
424
86
88
421
92
419
418
78
416
4...

result:

ok q=100000

Test #109:

score: 0
Accepted
time: 86ms
memory: 21228kb

input:

10000 100000
637 1
1879 1
1 2512
1 3578
3828 1
4117 1
1 4420
4468 1
4698 1
1 6029
6048 1
6553 1
6615 1
1 6970
7457 1
7626 1
1 7647
1 9559
9862 1
2 362
2 2514
2764 2
2 2982
3679 2
6566 2
2 8237
8441 2
8654 2
8754 2
8796 2
2 8905
9184 2
3 1285
3 1795
2932 3
3 3025
3 3149
3 3537
5987 3
3 6361
3 6710
3 ...

output:

1
500
3
4
497
496
5
494
493
492
6
7
8
488
487
486
9
484
483
10
481
480
13
478
477
14
475
17
22
472
24
25
469
468
26
27
29
30
463
32
461
34
36
38
41
44
47
454
453
452
49
450
50
448
447
52
53
444
443
442
441
59
64
67
68
69
435
70
73
74
431
430
75
428
427
426
76
424
79
81
449
446
445
418
440
439
415
43...

result:

ok q=100000

Test #110:

score: 0
Accepted
time: 96ms
memory: 21336kb

input:

10000 100000
6 1
1 399
891 1
1 1247
1269 1
1 1839
1 4072
4089 1
1 4245
1 4901
5339 1
1 7182
7459 1
8149 1
8208 1
1 8881
8937 1
1 9259
2 997
2 1065
2 2100
2 2796
2 3802
2 4857
2 5518
2 5539
5952 2
2 5973
7487 2
2 8574
2 9917
61 3
3 70
591 3
3 594
3 1502
3 1606
3 1616
3106 3
3 3523
3 3742
3 4162
4550 ...

output:

5
6
8
498
9
11
12
494
493
492
491
490
489
15
487
486
19
21
22
23
29
30
36
478
477
476
475
474
473
472
40
41
469
42
44
46
465
47
48
462
461
460
49
51
457
52
53
454
453
56
57
450
59
448
447
60
62
444
63
442
441
440
68
438
437
436
69
434
70
71
431
430
72
428
427
75
425
79
84
422
421
420
419
85
88
416
9...

result:

ok q=100000

Test #111:

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

input:

10000 100000
1 362
793 1
1 2340
1 2929
1 3619
1 3663
1 3789
6135 1
6331 1
6700 1
1 6901
7815 1
8192 1
1 8615
8676 1
1 8849
1 9273
1 9310
323 2
512 2
2 847
2 967
2 970
1006 2
1716 2
2102 2
2 2739
3298 2
2 3444
2 3472
3889 2
2 4569
2 5985
6892 2
7135 2
7675 2
7854 2
7871 2
8179 2
8656 2
8719 2
2 8799
...

output:

5
7
499
498
8
9
11
12
14
492
16
17
489
20
487
486
485
25
483
482
481
27
479
478
477
476
475
474
30
31
33
34
38
468
467
39
40
464
463
462
461
460
42
458
46
456
48
50
453
452
51
53
449
55
57
60
445
62
63
65
66
440
439
438
67
436
435
434
433
69
72
73
429
428
427
426
75
424
76
77
78
79
85
90
93
416
415
...

result:

ok q=100000

Test #112:

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

input:

10000 100000
1 53
1 1122
1949 1
1965 1
1 2760
1 6345
6354 1
1 6764
1 7825
1 8453
8734 1
9046 1
1 9160
9875 1
2 29
167 2
754 2
2 867
1007 2
1040 2
2 1421
2752 2
2 3046
2 3444
2 3627
2 4830
2 5453
2 6492
2 8157
2 8480
2 9226
2 9460
9525 2
369 3
572 3
3 648
1053 3
3 1356
3 2369
3153 3
3155 3
3 5471
604...

output:

2
3
499
498
497
496
6
7
8
492
12
490
17
488
487
20
485
21
483
22
25
26
479
478
477
28
30
31
473
472
471
470
32
33
36
466
41
464
463
43
461
44
46
50
51
456
455
454
453
452
53
450
54
57
58
446
445
62
66
67
68
70
73
438
437
80
81
84
433
85
431
86
429
428
427
88
425
89
423
90
94
97
419
101
417
416
415
4...

result:

ok q=100000

Test #113:

score: 0
Accepted
time: 50ms
memory: 21264kb

input:

10000 100000
303 1
1 306
1 309
603 1
1 624
1 713
1 954
1019 1
1921 1
2013 1
1 2239
2768 1
1 2899
4285 1
4773 1
1 5281
1 5596
5739 1
5755 1
5849 1
6228 1
1 7029
1 7255
7597 1
7679 1
9099 1
1 9342
966 2
2 1630
2 1984
2339 2
2 2603
2 3021
2 3661
2 3766
6428 2
2 7230
2 7652
7773 2
7997 2
9437 2
9475 2
9...

output:

1
2
499
3
6
496
7
8
493
11
13
15
17
488
487
486
21
23
483
24
481
26
479
478
477
476
475
30
31
472
32
33
37
468
467
42
44
464
463
50
51
460
56
458
457
456
57
61
453
452
451
63
64
66
69
446
71
444
443
442
72
440
439
438
437
73
435
434
74
432
75
80
82
83
427
426
85
424
423
86
421
87
89
92
417
416
415
9...

result:

ok q=100000

Test #114:

score: 0
Accepted
time: 107ms
memory: 21272kb

input:

10000 100000
1 687
1 2238
2339 1
2540 1
3744 1
1 4048
1 5868
1 6041
7833 1
8786 1
9222 1
935 2
2 1185
2 1659
1973 2
2 2048
2 2569
3163 2
3286 2
2 4612
5511 2
2 5535
5942 2
2 6222
2 6365
2 6547
6954 2
2 7976
8670 2
9133 2
2 9507
1116 3
1283 3
3 1886
3 2675
4460 3
5444 3
3 6072
3 7681
8072 3
8104 3
3 ...

output:

2

result:

ok q=100000

Test #115:

score: 0
Accepted
time: 103ms
memory: 21328kb

input:

10000 100000
16 1
1 226
1 546
1 751
1 1332
1 2446
2702 1
2853 1
4522 1
4669 1
1 4771
1 5035
5108 1
1 5221
1 5265
5519 1
8583 1
1 8612
1 9249
1 9798
20 2
2 312
534 2
689 2
1484 2
2304 2
2351 2
2 3520
2 3886
4324 2
4432 2
4630 2
4977 2
6737 2
7547 2
2 7610
2 7638
7669 2
7678 2
7894 2
2 8781
2 8824
904...

output:

275
404
472
489
589
93
742
756
774
133
326
238
277
83
353
736
114
447
778
735
995
826
1007
15
55
266
869
706
1036
1040
1066
1073
1176
1324
1398
940
1475
398
1375
1489
1516
485
902
1067
1527
1556
567
1173
1305
734
1575
1586
311
758
927
516
538
951
966
237
1194
1456
1996
1361
1595
1611
126
983
703
128...

result:

ok q=100000

Test #116:

score: 0
Accepted
time: 87ms
memory: 21324kb

input:

10000 100000
1 634
1 773
973 1
1993 1
1 2206
1 2258
1 2674
2934 1
3289 1
1 3486
1 3665
3870 1
1 4202
1 4222
4916 1
1 5131
5341 1
1 5589
1 7234
1 7419
1 7603
1 7647
1 7871
1 7887
8704 1
2 165
2 334
2 896
2 1110
1438 2
1649 2
1824 2
2158 2
2 2205
2781 2
2 2912
2 4077
2 4501
4528 2
2 5391
2 5496
2 5811...

output:

0
1508
4333
4747
4708
7873
7890
9421
9687
236
1332
1465
2850
3772
29
246
5490
5509
1176
1975
968
2119
2153
261
584
1510
1921
2393
2933
2934
2935
368
1477
2936
2937
2938
1546
542
744
2939
2940
2941
2942
2943
2944
322
2945
2946
232
351
438
847
1158
1602
1931
2077
2181
2947
2948
2949
1460
2950
2951
295...

result:

ok q=100000

Test #117:

score: 0
Accepted
time: 84ms
memory: 21256kb

input:

10000 100000
141 1
1 864
1 1515
1 1659
1 1665
1 1986
1 2432
2546 1
1 2598
1 2721
2792 1
3557 1
3736 1
1 7164
7510 1
1 9187
9424 1
2 2738
2 2936
3033 2
2 4575
4971 2
2 5719
6196 2
2 6465
2 6500
2 6665
2 7093
7520 2
2 7675
2 9723
3 130
3 279
755 3
3 964
1475 3
1750 3
3 1879
3 1961
3 2223
3 3125
3 3484...

output:

0
7607
3860
299
1280
1413
2408
3861
3862
3863
1883
3864
110
2339
1780
3865
3866
3867
3868
3869
218
1498
1814
3870
3871
3872
3873
3874
3875
3876
3877
4185
4294
1824
2014
2689
3165
3901
4543
4990
5470
6001
318
402
1627
3595
5041
6131
3946
6132
6133
6134
3304
306
4137
4169
12
4400
5554
6135
6136
6137
6...

result:

ok q=100000

Test #118:

score: 0
Accepted
time: 78ms
memory: 21248kb

input:

10000 100000
1 496
1 976
1674 1
1 2091
1 2796
1 3047
1 3734
1 4361
1 4620
6855 1
1 6896
1 8073
8352 1
1 8572
8781 1
1 8857
1 8915
1 9035
1 9294
9490 1
9985 1
673 2
855 2
2 1012
1711 2
2 1902
2426 2
2 2597
2960 2
2 4925
2 5659
7946 2
7990 2
2 8450
2 8638
2 8646
2 8918
9379 2
3 443
3 458
3 1247
3 1405...

output:

20635
29135
4243
18271
19650
24146
29964
3482
5947
11811
2766
7597
10929
11208
5669
11209
11210
11211
897
3439
4434
11212
11213
11214
11215
337
4227
5836
8877
9877
4836
10534
11216
11217
11218
1133
1628
1239
349
857
1772
3963
6057
6113
6441
7562
7850
9777
10371
4366
10523
4230
4410
10539
6562
10941
...

result:

ok q=100000

Test #119:

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

input:

10000 100000
155 1
1 312
458 1
1 1772
1 2247
2334 1
1 2939
1 3031
4298 1
1 4460
1 6773
6873 1
7230 1
7285 1
7408 1
8385 1
1 8469
1 9022
9310 1
245 2
883 2
2 1068
1159 2
2 1844
2 2177
2 2407
2670 2
2820 2
2 2948
3701 2
3801 2
2 4259
2 4406
4662 2
5265 2
2 6295
7931 2
9316 2
2 9595
88 3
125 3
1259 3
3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
4129
6177
12294
19229
19563
20671
38728
42521
42522
42523
42524
42525
3917
7655
10294
6092
13764
13765
13766
13767
13768
13769
13770
13771
13772
13773
13774
13775
13776
9738
14398
14499
14504
19361
23079
25894
26817
26952
11540
14267
26737
27179
27224
31762
10293
21202
2833...

result:

ok q=100000

Test #120:

score: 0
Accepted
time: 28ms
memory: 21340kb

input:

10000 100000
121 1
1 242
1 1247
1325 1
1 1445
2211 1
2687 1
3212 1
1 3458
1 4405
1 4473
5781 1
1 5987
6973 1
7680 1
1 9000
9059 1
1 9514
9600 1
51 2
2 693
1286 2
1391 2
2 1705
2 3339
3471 2
2 3864
2 5097
2 5130
5658 2
2 6647
6819 2
2 7138
2 7764
2 7810
8298 2
2 8369
8894 2
2 9880
3 53
3 625
3 779
14...

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 q=100000

Test #121:

score: 0
Accepted
time: 22ms
memory: 21112kb

input:

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

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 q=100000

Test #122:

score: 0
Accepted
time: 38ms
memory: 21072kb

input:

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

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 q=100000

Test #123:

score: 0
Accepted
time: 23ms
memory: 21144kb

input:

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

output:

1
0
500
0
499
0
498
0
497
0
496
0
495
0
494
0
493
0
492
0
491
0
490
0
489
0
488
0
487
0
486
0
485
0
484
0
483
0
482
0
481
0
480
0
479
0
478
0
477
0
476
0
475
0
474
0
473
0
472
0
471
0
470
0
469
0
468
0
467
0
466
0
465
0
464
0
463
0
462
0
461
0
460
0
459
0
458
0
457
0
456
0
455
0
454
0
453
0
452
0
45...

result:

ok q=100000

Test #124:

score: 0
Accepted
time: 23ms
memory: 21012kb

input:

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

output:

1
500
0
499
0
498
497
0
496
495
0
0
494
0
0
0
493
0
0
492
491
0
0
0
490
489
0
488
487
486
485
484
483
482
0
0
481
480
479
478
477
0
476
0
0
0
0
475
474
473
0
472
471
0
0
0
0
0
0
470
0
469
0
468
467
466
465
464
463
0
0
0
0
0
0
0
0
462
0
461
0
0
460
459
458
457
0
0
0
456
0
455
454
453
0
452
451
450
0
...

result:

ok q=100000

Test #125:

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

input:

9970 100000
1 2
3 1
1 5
7 1
1 9
11 1
1 13
15 1
17 1
19 1
21 1
1 23
25 1
1 27
1 29
1 31
1 33
35 1
37 1
39 1
1 41
43 1
45 1
47 1
1 49
1 51
1 53
1 55
1 57
1 59
61 1
1 63
65 1
1 67
69 1
71 1
1 73
1 75
77 1
1 79
1 81
83 1
1 85
1 87
1 89
1 91
1 93
1 95
1 97
1 99
101 1
1 103
1 105
1 107
109 1
111 1
113 1
1...

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 q=100000

Test #126:

score: 0
Accepted
time: 37ms
memory: 21012kb

input:

9970 100000
2 1
3 1
5 1
1 7
9 1
1 11
13 1
1 15
17 1
19 1
1 21
23 1
1 25
1 27
29 1
1 31
33 1
35 1
37 1
1 39
41 1
43 1
1 45
1 47
49 1
1 51
53 1
55 1
1 57
1 59
61 1
63 1
1 65
1 67
1 69
1 71
73 1
1 75
1 77
79 1
1 81
1 83
1 85
87 1
89 1
91 1
93 1
95 1
1 97
1 99
1 101
103 1
105 1
107 1
109 1
111 1
1 113
1...

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 q=100000

Test #127:

score: 0
Accepted
time: 19ms
memory: 20968kb

input:

9970 100000
1 2
1 3
1 5
1 7
9 1
11 1
13 1
1 15
1 17
19 1
1 21
1 23
25 1
1 27
1 29
1 31
1 33
35 1
37 1
1 39
41 1
1 43
45 1
1 47
1 49
51 1
53 1
55 1
1 57
59 1
1 61
1 63
1 65
1 67
1 69
1 71
1 73
75 1
77 1
79 1
1 81
83 1
85 1
87 1
89 1
1 91
93 1
1 95
97 1
1 99
101 1
103 1
1 105
1 107
1 109
111 1
1 113
1...

output:

1
0
4986
500
499
498
497
0
5000
496
4999
495
494
493
492
0
4998
0
4997
0
4996
491
4995
490
4994
489
4993
0
4992
0
488
487
4991
486
485
0
4990
484
483
0
482
481
480
0
479
478
4989
477
4988
476
475
0
4987
0
5001
0
5500
0
5499
0
474
473
472
0
471
0
470
469
5498
468
467
466
465
464
5497
0
5496
0
5495
46...

result:

ok q=100000

Test #128:

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

input:

9970 100000
1 2
1 3
1 5
7 1
1 9
1 11
1 13
1 15
17 1
1 19
21 1
23 1
25 1
1 27
1 29
1 31
33 1
35 1
1 37
39 1
1 41
1 43
1 45
47 1
49 1
1 51
53 1
1 55
57 1
59 1
61 1
63 1
65 1
67 1
1 69
1 71
1 73
1 75
1 77
79 1
81 1
1 83
85 1
87 1
1 89
1 91
93 1
1 95
1 97
1 99
101 1
103 1
1 105
107 1
109 1
1 111
1 113
1...

output:

0
0
0
0
1
4986
5000
4999
500
499
4998
498
497
4997
4996
4995
0
496
495
4994
4993
494
493
492
491
490
489
488
487
486
485
484
0
483
0
4992
4991
482
481
0
0
480
479
478
4990
0
4989
0
0
477
476
0
0
0
0
0
0
475
474
473
472
471
470
469
468
4988
4987
5001
5500
0
0
467
466
465
464
0
463
0
462
461
460
459
4...

result:

ok q=100000

Test #129:

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

input:

9970 100000
3 1
1 4
7 1
1 10
13 1
16 1
1 19
22 1
25 1
1 28
31 1
1 34
37 1
1 40
43 1
1 46
49 1
52 1
1 55
58 1
1 61
1 64
1 67
1 70
73 1
1 76
1 79
1 82
1 85
1 88
91 1
94 1
97 1
100 1
103 1
1 106
109 1
112 1
1 115
1 118
121 1
124 1
1 127
130 1
133 1
136 1
139 1
1 142
145 1
1 148
1 151
1 154
1 157
160 1
...

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 q=100000

Test #130:

score: 0
Accepted
time: 39ms
memory: 21012kb

input:

9970 100000
3 1
1 4
7 1
10 1
13 1
1 16
19 1
1 22
25 1
1 28
1 31
1 34
1 37
1 40
43 1
1 46
1 49
1 52
1 55
1 58
1 61
1 64
1 67
1 70
73 1
1 76
79 1
1 82
1 85
1 88
1 91
1 94
1 97
1 100
1 103
1 106
1 109
1 112
1 115
118 1
1 121
124 1
127 1
130 1
1 133
1 136
1 139
1 142
1 145
1 148
151 1
154 1
1 157
1 160
...

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 q=100000

Test #131:

score: 0
Accepted
time: 28ms
memory: 21076kb

input:

9970 100000
2 1
3 1
1 4
1 7
10 1
1 13
1 16
19 1
22 1
25 1
1 28
1 31
1 34
37 1
1 40
1 43
1 46
49 1
1 52
1 55
1 58
1 61
1 64
67 1
1 70
73 1
1 76
1 79
82 1
1 85
1 88
91 1
94 1
97 1
100 1
1 103
1 106
109 1
1 112
115 1
118 1
121 1
1 124
1 127
1 130
133 1
1 136
139 1
1 142
145 1
1 148
1 151
1 154
1 157
16...

output:

2
1
6648
499
7000
3326
6999
0
3500
3499
3498
498
497
3497
3496
496
3495
495
3494
3493
6998
494
6997
3492
3491
493
492
491
6996
0
6995
490
489
488
487
486
485
484
3490
483
3489
0
6994
3488
3487
0
6993
0
3486
482
3485
481
3484
480
479
3483
478
477
476
3482
3481
0
3480
3479
6992
3478
3477
475
474
0
347...

result:

ok q=100000

Test #132:

score: 0
Accepted
time: 20ms
memory: 21072kb

input:

9970 100000
1 2
1 3
4 1
7 1
1 10
13 1
16 1
1 19
22 1
25 1
1 28
1 31
1 34
1 37
40 1
43 1
46 1
1 49
1 52
1 55
1 58
1 61
64 1
1 67
70 1
1 73
76 1
1 79
82 1
1 85
1 88
91 1
1 94
1 97
1 100
1 103
1 106
109 1
1 112
1 115
118 1
121 1
124 1
127 1
130 1
133 1
1 136
1 139
142 1
145 1
1 148
151 1
1 154
1 157
1 ...

output:

2
1
6648
3326
7000
6999
0
0
3500
3499
3498
499
3497
3496
3495
3494
498
3493
3492
3491
3490
3489
497
496
495
494
493
492
491
490
489
488
487
3488
486
485
484
483
482
481
480
479
478
3487
6998
6997
0
0
3486
477
3485
3484
3483
3482
3481
3480
3479
3478
6996
476
475
474
473
0
472
471
470
469
468
467
466
...

result:

ok q=100000

Test #133:

score: 0
Accepted
time: 34ms
memory: 21012kb

input:

9970 100000
3 1
1 5
1 9
1 13
17 1
21 1
25 1
1 29
33 1
1 37
1 41
45 1
49 1
53 1
57 1
61 1
65 1
1 69
1 73
1 77
1 81
85 1
1 89
93 1
97 1
101 1
105 1
1 109
113 1
117 1
121 1
125 1
1 129
133 1
1 137
1 141
1 145
149 1
1 153
157 1
1 161
1 165
1 169
1 173
1 177
181 1
185 1
189 1
193 1
1 197
201 1
1 205
209 ...

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 q=100000

Test #134:

score: 0
Accepted
time: 37ms
memory: 21072kb

input:

9970 100000
1 2
1 3
1 5
9 1
1 13
1 17
1 21
1 25
29 1
1 33
37 1
1 41
45 1
1 49
1 53
1 57
1 61
65 1
69 1
73 1
1 77
1 81
1 85
1 89
1 93
1 97
101 1
105 1
109 1
1 113
1 117
121 1
125 1
1 129
1 133
137 1
1 141
145 1
1 149
153 1
1 157
1 161
1 165
169 1
173 1
1 177
1 181
1 185
1 189
193 1
1 197
1 201
205 1
...

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
1
2
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 q=100000

Test #135:

score: 0
Accepted
time: 19ms
memory: 21012kb

input:

9970 100000
1 2
1 5
9 1
13 1
17 1
1 21
25 1
1 29
33 1
1 37
41 1
1 45
1 49
1 53
1 57
61 1
65 1
69 1
73 1
77 1
1 81
85 1
89 1
93 1
1 97
101 1
1 105
1 109
1 113
1 117
1 121
1 125
129 1
1 133
1 137
1 141
1 145
1 149
153 1
1 157
1 161
165 1
169 1
1 173
177 1
181 1
1 185
189 1
193 1
197 1
1 201
205 1
1 20...

output:

2494
1
500
499
498
497
496
495
494
493
2500
2499
2498
2497
492
491
490
489
2495
4988
5000
0
4999
2496
488
487
486
2501
3000
2999
4998
4997
7479
2998
7500
485
7499
0
4996
4995
4994
4993
2997
2996
2995
484
2994
4992
4991
2993
2992
2991
2990
2989
2988
2987
2986
2985
2984
4990
483
482
481
480
479
478
47...

result:

ok q=100000

Test #136:

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

input:

9970 100000
1 3
5 1
9 1
13 1
1 17
21 1
25 1
1 29
33 1
1 37
1 41
1 45
1 49
53 1
57 1
61 1
65 1
69 1
73 1
77 1
1 81
85 1
1 89
1 93
1 97
1 101
105 1
109 1
113 1
1 117
1 121
1 125
129 1
1 133
137 1
141 1
145 1
1 149
153 1
157 1
1 161
1 165
1 169
1 173
1 177
181 1
1 185
1 189
193 1
1 197
1 201
1 205
1 20...

output:

0
0
0
0
4987
7479
1
2494
5000
4999
7500
2500
2499
2498
500
499
498
497
496
495
494
7499
4998
4997
4996
7498
7497
4995
4994
7496
4993
4992
7495
7494
493
7493
4991
492
491
490
2497
2496
2495
489
488
487
486
485
484
483
0
0
4990
4989
4988
5001
5500
0
0
0
482
481
480
479
478
477
476
475
474
473
472
471
...

result:

ok q=100000

Test #137:

score: 0
Accepted
time: 39ms
memory: 20996kb

input:

9970 100000
3 1
4 1
1 5
6 1
11 1
1 16
1 21
1 26
1 31
36 1
41 1
1 46
1 51
1 56
61 1
66 1
1 71
76 1
81 1
86 1
91 1
1 96
101 1
106 1
111 1
1 116
1 121
1 126
131 1
136 1
1 141
146 1
151 1
156 1
1 161
1 166
171 1
176 1
181 1
186 1
1 191
196 1
201 1
206 1
211 1
216 1
221 1
226 1
231 1
1 236
1 241
1 246
1 ...

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 q=100000

Test #138:

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

input:

9970 100000
3 1
6 1
11 1
1 16
1 21
26 1
1 31
1 36
1 41
46 1
51 1
56 1
61 1
1 66
1 71
1 76
81 1
86 1
1 91
96 1
1 101
1 106
1 111
116 1
1 121
126 1
131 1
1 136
141 1
1 146
151 1
156 1
161 1
166 1
1 171
176 1
1 181
186 1
1 191
196 1
1 201
206 1
1 211
1 216
1 221
1 226
1 231
1 236
241 1
1 246
251 1
1 25...

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 q=100000

Test #139:

score: 0
Accepted
time: 27ms
memory: 21128kb

input:

9970 100000
1 2
1 6
11 1
16 1
1 21
26 1
31 1
1 36
41 1
46 1
51 1
56 1
1 61
66 1
1 71
1 76
81 1
1 86
91 1
1 96
1 101
106 1
111 1
116 1
121 1
126 1
1 131
1 136
141 1
1 146
151 1
156 1
161 1
166 1
171 1
176 1
181 1
186 1
191 1
1 196
1 201
206 1
1 211
1 216
1 221
1 226
1 231
1 236
241 1
246 1
1 251
256 ...

output:

1995
0
1996
3990
5984
4000
3999
3998
1
3997
500
499
498
497
496
3996
3995
495
494
493
492
491
2000
1998
1997
1999
3994
3993
490
489
488
3992
6000
0
487
0
7978
2001
486
485
484
483
482
481
5999
0
480
0
2500
2499
2498
479
478
477
476
3991
4001
2497
475
474
473
472
471
470
469
468
467
466
465
464
463
4...

result:

ok q=100000

Test #140:

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

input:

9970 100000
1 2
3 1
6 1
1 11
1 16
1 21
1 26
31 1
36 1
41 1
1 46
51 1
56 1
1 61
1 66
71 1
1 76
81 1
86 1
91 1
96 1
1 101
106 1
111 1
116 1
121 1
126 1
131 1
136 1
1 141
1 146
151 1
1 156
1 161
1 166
1 171
1 176
1 181
1 186
191 1
1 196
201 1
206 1
1 211
216 1
221 1
226 1
231 1
1 236
1 241
1 246
251 1
...

output:

0
5984
6000
5999
5998
5997
5996
1
5995
5994
5993
5992
1996
2000
1999
1998
1997
2001
2500
2499
2498
5991
5990
5989
500
499
498
497
496
495
494
493
492
491
490
489
488
487
486
485
484
483
482
481
480
479
478
477
476
475
474
473
472
471
470
469
468
467
466
465
464
463
462
461
460
459
458
457
2497
2496
...

result:

ok q=100000

Test #141:

score: 0
Accepted
time: 40ms
memory: 21152kb

input:

9970 100000
2 1
1 6
1 7
13 1
19 1
1 25
1 31
1 37
1 43
1 49
1 55
1 61
1 67
73 1
79 1
1 85
91 1
1 97
103 1
109 1
115 1
121 1
127 1
1 133
1 139
145 1
151 1
157 1
1 163
1 169
175 1
181 1
187 1
1 193
199 1
1 205
1 211
1 217
223 1
1 229
1 235
241 1
247 1
253 1
1 259
1 265
271 1
277 1
1 283
289 1
1 295
301...

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
3327
4991
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 q=100000

Test #142:

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

input:

9970 100000
2 1
1 3
4 1
1 6
7 1
1 13
1 19
1 25
1 31
1 37
43 1
1 49
1 55
61 1
67 1
1 73
79 1
85 1
1 91
1 97
1 103
109 1
115 1
121 1
1 127
133 1
1 139
145 1
1 151
157 1
163 1
1 169
175 1
181 1
187 1
193 1
1 199
205 1
1 211
217 1
223 1
229 1
1 235
241 1
1 247
1 253
259 1
265 1
271 1
1 277
1 283
289 1
2...

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 q=100000

Test #143:

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

input:

9970 100000
4 1
1 5
6 1
7 1
1 13
1 19
25 1
31 1
37 1
1 43
49 1
55 1
61 1
67 1
1 73
1 79
85 1
1 91
97 1
103 1
1 109
1 115
121 1
1 127
133 1
1 139
1 145
151 1
1 157
163 1
1 169
175 1
181 1
187 1
1 193
1 199
1 205
211 1
1 217
1 223
229 1
235 1
1 241
247 1
253 1
1 259
265 1
1 271
1 277
1 283
1 289
1 295...

output:

2
0
1665
3
2000
1
498
497
1999
1998
1997
1996
496
495
494
493
492
491
490
489
488
487
486
485
484
483
482
481
480
479
478
477
1666
1667
3329
3500
4991
3499
5000
3498
3497
4990
476
475
6652
3496
474
473
472
471
470
1995
3495
469
468
3494
3493
4998
3492
4997
4996
1992
1991
1990
467
466
465
464
463
462...

result:

ok q=100000

Test #144:

score: 0
Accepted
time: 28ms
memory: 21020kb

input:

9970 100000
3 1
1 4
5 1
1 7
13 1
19 1
1 25
1 31
37 1
43 1
1 49
55 1
61 1
67 1
73 1
79 1
1 85
1 91
1 97
1 103
109 1
1 115
1 121
1 127
1 133
139 1
1 145
151 1
1 157
163 1
1 169
175 1
181 1
187 1
1 193
199 1
205 1
211 1
217 1
1 223
1 229
235 1
1 241
1 247
1 253
259 1
1 265
271 1
1 277
283 1
1 289
295 1...

output:

1
500
499
498
497
496
495
494
493
492
491
490
489
488
487
486
485
484
483
482
3
3328
481
479
478
477
476
475
474
473
472
471
470
469
468
467
2
1665
4990
6652
3327
2000
7000
6999
6998
5000
4999
4998
4997
3499
3498
3497
3496
3495
3494
3493
3492
3491
466
3490
3489
3488
3487
3486
3485
3484
3483
3482
499...

result:

ok q=100000

Test #145:

score: 0
Accepted
time: 38ms
memory: 21040kb

input:

9970 100000
3 1
6 1
1 7
1 8
15 1
1 22
29 1
1 36
43 1
1 50
1 57
1 64
71 1
1 78
1 85
92 1
1 99
1 106
1 113
1 120
1 127
1 134
141 1
148 1
1 155
162 1
169 1
176 1
183 1
190 1
197 1
204 1
211 1
1 218
225 1
1 232
239 1
246 1
1 253
1 260
1 267
1 274
281 1
1 288
1 295
302 1
309 1
1 316
1 323
330 1
1 337
344...

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 q=100000

Test #146:

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

input:

9970 100000
1 3
5 1
6 1
1 8
15 1
22 1
29 1
36 1
1 43
50 1
57 1
64 1
1 71
1 78
1 85
92 1
99 1
106 1
113 1
1 120
127 1
134 1
141 1
1 148
1 155
1 162
169 1
1 176
1 183
1 190
197 1
1 204
1 211
218 1
1 225
1 232
1 239
1 246
253 1
1 260
1 267
274 1
1 281
288 1
1 295
302 1
1 309
1 316
1 323
1 330
1 337
344...

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
1430
2856
7128
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 q=100000

Test #147:

score: 0
Accepted
time: 16ms
memory: 21040kb

input:

9970 100000
3 1
4 1
6 1
8 1
1 15
1 22
1 29
36 1
43 1
50 1
1 57
64 1
1 71
78 1
1 85
1 92
99 1
106 1
113 1
120 1
127 1
134 1
1 141
1 148
155 1
162 1
1 169
1 176
183 1
1 190
197 1
1 204
1 211
218 1
1 225
232 1
1 239
1 246
1 253
260 1
267 1
1 274
1 281
288 1
1 295
1 302
1 309
1 316
323 1
1 330
1 337
1 3...

output:

1428
1
500
499
498
497
496
2
3
4279
2855
1430
495
492
491
490
489
4500
1429
1500
1497
1496
1495
3000
2999
2998
488
487
486
0
485
484
5703
1494
483
482
481
2997
480
479
478
477
476
475
474
473
472
471
470
1493
1492
1491
1490
1489
4499
6000
2996
469
468
5999
4498
4497
7128
1488
1487
467
466
465
464
46...

result:

ok q=100000

Test #148:

score: 0
Accepted
time: 21ms
memory: 21072kb

input:

9970 100000
3 1
5 1
1 8
15 1
1 22
1 29
36 1
43 1
50 1
57 1
64 1
1 71
1 78
85 1
1 92
1 99
106 1
1 113
120 1
127 1
1 134
141 1
1 148
155 1
1 162
169 1
176 1
1 183
190 1
197 1
1 204
211 1
218 1
225 1
1 232
239 1
1 246
253 1
260 1
1 267
274 1
1 281
288 1
295 1
1 302
1 309
316 1
323 1
330 1
337 1
344 1
3...

output:

0
0
2855
1
1428
1500
1499
1498
500
499
498
497
496
495
494
493
492
491
490
489
1497
1427
1495
1494
1493
4281
5705
8552
1492
1491
1490
1489
1488
2
1487
1486
1485
1484
1483
1482
1481
1480
1479
1478
1477
1476
1475
1474
1473
1472
1471
1470
1469
1468
3000
2999
2998
2997
2996
2995
1429
2994
2993
2854
4279...

result:

ok q=100000

Test #149:

score: 0
Accepted
time: 40ms
memory: 21144kb

input:

9970 100000
2 1
1 3
1 4
5 1
7 1
8 1
1 9
1 17
25 1
1 33
1 41
1 49
1 57
1 65
73 1
1 81
1 89
1 97
1 105
1 113
121 1
1 129
137 1
145 1
1 153
161 1
169 1
177 1
1 185
193 1
201 1
209 1
1 217
1 225
233 1
241 1
1 249
257 1
265 1
1 273
1 281
289 1
297 1
305 1
1 313
321 1
329 1
1 337
345 1
353 1
1 361
1 369
1...

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 q=100000

Test #150:

score: 0
Accepted
time: 46ms
memory: 21076kb

input:

9970 100000
1 4
1 5
6 1
8 1
9 1
17 1
25 1
1 33
1 41
1 49
57 1
65 1
1 73
81 1
89 1
97 1
105 1
1 113
121 1
1 129
137 1
145 1
1 153
1 161
1 169
177 1
1 185
1 193
1 201
209 1
217 1
1 225
233 1
1 241
249 1
257 1
265 1
1 273
1 281
289 1
1 297
305 1
1 313
321 1
1 329
1 337
345 1
1 353
361 1
369 1
377 1
385...

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
4
1254
7486
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 q=100000

Test #151:

score: 0
Accepted
time: 28ms
memory: 21132kb

input:

9970 100000
1 3
1 6
8 1
1 9
17 1
25 1
33 1
1 41
1 49
57 1
65 1
73 1
81 1
89 1
1 97
105 1
113 1
121 1
1 129
1 137
1 145
1 153
161 1
169 1
177 1
1 185
193 1
1 201
209 1
1 217
1 225
233 1
1 241
249 1
257 1
265 1
1 273
281 1
289 1
1 297
1 305
1 313
1 321
1 329
1 337
345 1
353 1
1 361
1 369
1 377
385 1
1...

output:

1
1250
2500
2
2501
3000
2499
2999
3
1251
1252
3748
3747
6241
3999
1500
1497
3998
3997
1496
500
497
496
495
494
493
492
491
490
489
488
487
486
1495
1494
1493
485
484
483
482
481
480
479
478
477
476
475
474
473
3996
472
471
470
469
468
467
466
465
464
1492
1491
463
462
461
460
459
458
457
456
455
454...

result:

ok q=100000

Test #152:

score: 0
Accepted
time: 20ms
memory: 21064kb

input:

9970 100000
2 1
1 3
5 1
1 9
17 1
25 1
1 33
41 1
1 49
1 57
65 1
73 1
81 1
89 1
1 97
105 1
1 113
121 1
1 129
1 137
145 1
153 1
1 161
1 169
1 177
185 1
193 1
201 1
1 209
1 217
225 1
1 233
241 1
249 1
257 1
265 1
1 273
1 281
1 289
297 1
1 305
1 313
1 321
1 329
337 1
345 1
353 1
1 361
1 369
377 1
1 385
1...

output:

0
0
3746
1252
3747
6241
6500
1
500
6499
6498
6497
6496
6495
2500
2
1250
2499
2501
3748
4994
4995
6494
499
497
496
495
494
493
492
491
490
489
488
487
486
485
484
483
482
3
1251
5000
4998
3000
2999
2998
2997
4000
481
479
478
477
476
475
474
473
472
471
470
469
468
467
466
465
464
463
462
461
460
459
...

result:

ok q=100000

Test #153:

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

input:

1000 100000
1 5
17 1
22 1
33 1
1 34
35 1
41 1
1 55
1 56
60 1
75 1
76 1
1 77
88 1
1 89
1 93
1 95
1 96
97 1
98 1
1 103
1 105
108 1
1 112
1 115
116 1
143 1
1 147
156 1
164 1
1 168
183 1
188 1
197 1
198 1
199 1
210 1
1 213
215 1
1 217
223 1
224 1
225 1
228 1
1 233
236 1
240 1
249 1
250 1
258 1
259 1
1 2...

output:

1

result:

ok q=100000

Test #154:

score: 0
Accepted
time: 33ms
memory: 7096kb

input:

1000 100000
1 10
1 16
21 1
23 1
1 28
30 1
1 31
1 36
39 1
1 44
1 45
1 48
1 57
61 1
62 1
1 63
67 1
69 1
77 1
1 78
1 84
1 91
94 1
96 1
1 100
1 104
112 1
115 1
1 120
1 124
128 1
130 1
137 1
148 1
1 161
164 1
170 1
1 173
1 185
188 1
189 1
1 192
1 195
1 200
207 1
1 210
1 219
230 1
237 1
239 1
245 1
247 1
...

output:

24
500
54
64
10
101
87
120
129
133
75
66
32
497
11
41
59
80
7
1
2
3
479
39
485
68
14
73
490
82
30
15
470
468
33
22
4
464
463
462
461
23
466
35
457
45
46
454
476
452
49
63
449
77
42
447
79
444
443
442
91
440
459
453
70
436
435
434
92
93
95
448
429
98
100
111
112
114
116
465
56
118
123
125
417
103
86
...

result:

ok q=100000

Test #155:

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

input:

1000 100000
1 10
1 13
14 1
16 1
1 19
21 1
32 1
1 39
40 1
1 44
49 1
1 51
52 1
1 54
1 56
61 1
63 1
70 1
1 73
1 83
1 87
1 99
101 1
104 1
111 1
114 1
119 1
121 1
122 1
126 1
1 130
133 1
135 1
1 146
150 1
158 1
170 1
183 1
1 184
185 1
186 1
187 1
1 190
192 1
196 1
205 1
208 1
223 1
227 1
1 235
1 242
244 ...

output:

740
654
67
693
101
460
519
325
17
536
736
795
774
33
186
368
671
493
62
137
165
95
209
400
85
222
150
258
412
115
65
157
252
118
226
449
409
114
120
131
501
582
296
247
316
498
595
66
40
248
331
462
35
103
459
365
601
482
406
266
414
160
430
5
47
130
193
211
991
580
986
585
586
587
433
588
589
590
5...

result:

ok q=100000

Test #156:

score: 0
Accepted
time: 34ms
memory: 6976kb

input:

1000 100000
1 2
3 1
5 1
1 8
9 1
10 1
1 11
19 1
21 1
42 1
44 1
45 1
1 46
1 67
69 1
1 75
1 87
1 88
100 1
103 1
114 1
121 1
1 123
127 1
131 1
1 143
1 149
151 1
153 1
159 1
1 163
1 174
176 1
1 185
1 186
191 1
1 194
1 205
210 1
1 215
1 217
1 219
1 220
222 1
1 229
232 1
234 1
1 237
240 1
1 241
245 1
1 247...

output:

0
0
0
0
0
0
0
686
186
20
228
4
240
33
335
387
408
190
395
419
453
532
617
116
355
643
713
767
781
6
420
608
754
828
62
862
441
467
657
829
510
715
912
34
927
945
141
151
344
204
280
380
515
540
174
318
557
980
603
620
624
709
768
249
845
886
291
881
92
295
559
970
595
670
2
481
466
465
464
463
462
4...

result:

ok q=100000

Test #157:

score: 0
Accepted
time: 36ms
memory: 6988kb

input:

1000 100000
1 6
1 12
18 1
19 1
34 1
1 37
41 1
53 1
58 1
1 63
1 66
1 70
73 1
1 80
1 82
94 1
1 104
1 110
1 112
1 114
1 115
118 1
121 1
126 1
131 1
136 1
1 137
139 1
1 145
146 1
148 1
1 149
1 159
1 161
164 1
170 1
186 1
189 1
191 1
193 1
1 197
1 206
207 1
208 1
212 1
224 1
1 225
1 226
228 1
229 1
233 1...

output:

478
570
373
1020
1458
1576
239
1489
1680
1822
329
179
751
83
1158
1165
1464
1569
1712
1831
758
801
823
999
983
1005
299
1236
1248
201
390
1295
1385
1431
1433
1445
1631
1772
546
732
1127
1600
738
1729
272
469
531
706
711
841
1265
1716
1777
1800
1988
1845
1890
1916
1943
1962
1973
1976
214
170
409
462
...

result:

ok q=100000

Test #158:

score: 0
Accepted
time: 37ms
memory: 7016kb

input:

1000 100000
1 10
1 20
23 1
26 1
32 1
35 1
1 41
47 1
1 52
1 54
57 1
1 58
61 1
68 1
71 1
1 82
1 85
90 1
103 1
1 114
1 124
125 1
129 1
1 133
1 135
139 1
140 1
1 143
1 158
1 160
1 161
164 1
1 169
174 1
181 1
186 1
187 1
188 1
189 1
199 1
1 208
1 227
1 228
1 232
1 240
1 243
250 1
1 255
260 1
270 1
272 1
...

output:

0
0
157
2131
4522
6322
7500
8680
372
700
769
1157
1902
2475
2539
4672
4738
1308
1896
4269
4881
5093
5152
2652
5649
5938
6058
6669
7273
7424
7513
965
1364
1765
2352
2951
3316
821
1016
1217
2006
3583
3730
3943
3540
2251
3414
3634
3995
4178
4638
153
746
946
2938
3127
3713
4755
4797
5391
5522
5593
5638
...

result:

ok q=100000

Test #159:

score: 0
Accepted
time: 25ms
memory: 7076kb

input:

1000 100000
5 1
1 11
1 20
1 37
43 1
44 1
47 1
48 1
54 1
1 63
69 1
1 70
72 1
73 1
83 1
84 1
1 86
1 93
1 94
1 95
1 101
1 108
114 1
115 1
124 1
137 1
1 141
1 144
1 151
158 1
159 1
160 1
167 1
175 1
181 1
1 183
1 191
1 196
1 198
1 203
1 213
1 215
216 1
239 1
245 1
246 1
249 1
1 254
261 1
264 1
277 1
289...

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 q=100000

Test #160:

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

input:

1000 100000
2 1
15 1
1 18
21 1
1 23
33 1
52 1
54 1
55 1
1 56
1 57
1 61
62 1
1 66
69 1
1 72
1 73
1 75
79 1
1 85
87 1
1 88
1 89
95 1
104 1
121 1
1 123
1 127
1 131
1 135
1 136
137 1
1 139
1 148
150 1
1 156
1 162
1 189
192 1
193 1
1 194
1 197
1 209
1 213
1 216
1 218
220 1
221 1
222 1
1 230
248 1
1 249
1...

output:

4

result:

ok q=100000

Test #161:

score: 0
Accepted
time: 34ms
memory: 7008kb

input:

1000 100000
5 1
11 1
1 15
23 1
25 1
1 26
1 27
1 30
35 1
39 1
1 49
1 53
1 57
1 72
1 73
1 78
1 81
83 1
1 85
1 87
88 1
96 1
101 1
1 107
110 1
1 112
116 1
118 1
1 121
1 123
124 1
125 1
131 1
134 1
1 137
1 140
141 1
143 1
155 1
1 157
1 168
171 1
177 1
182 1
184 1
185 1
1 187
193 1
1 206
207 1
1 208
209 1...

output:

3
500
4
5
7
8
495
494
10
12
491
13
499
488
487
486
498
497
483
482
496
480
493
478
477
492
490
15
473
16
19
470
14
472
469
466
465
464
475
462
461
460
459
463
457
456
476
20
453
23
451
25
449
26
39
40
41
455
443
444
481
440
28
438
32
436
441
44
47
432
11
430
429
428
46
426
425
49
423
51
52
54
57
448...

result:

ok q=100000

Test #162:

score: 0
Accepted
time: 27ms
memory: 7080kb

input:

1000 100000
1 6
7 1
1 12
1 22
1 25
1 29
1 31
36 1
45 1
1 67
75 1
1 81
85 1
1 89
95 1
97 1
1 103
115 1
123 1
125 1
1 129
133 1
137 1
148 1
1 155
158 1
178 1
179 1
1 181
1 187
1 188
205 1
207 1
208 1
1 211
1 214
1 219
1 223
231 1
1 237
239 1
1 242
243 1
251 1
256 1
1 260
262 1
269 1
270 1
271 1
275 1
...

output:

1
500
499
3
4
496
5
8
9
492
10
490
489
488
11
486
12
484
14
482
481
13
15
16
498
497
475
474
473
2
495
494
6
7
467
493
465
464
491
462
461
460
487
485
457
483
479
480
453
452
451
450
449
478
477
18
445
444
443
442
21
23
439
438
437
25
28
34
433
432
431
430
429
35
36
40
425
42
423
471
421
422
29
45
4...

result:

ok q=100000

Test #163:

score: 0
Accepted
time: 37ms
memory: 7024kb

input:

1000 100000
3 1
8 1
9 1
1 16
28 1
45 1
1 49
1 55
1 56
57 1
66 1
68 1
1 70
1 74
78 1
1 84
1 85
86 1
87 1
97 1
99 1
103 1
105 1
1 107
1 111
1 112
1 127
130 1
1 133
1 134
142 1
143 1
149 1
161 1
167 1
1 168
172 1
1 174
1 179
1 190
193 1
1 195
1 202
205 1
1 209
216 1
217 1
218 1
1 219
1 229
1 234
236 1
...

output:

3
4
5
498
6
496
7
494
8
9
10
12
14
17
21
22
28
484
483
29
31
480
36
37
27
38
39
474
40
472
41
470
42
468
467
466
47
464
463
49
52
481
459
55
56
57
455
454
59
61
66
68
71
448
447
446
445
444
443
73
77
440
78
438
437
79
83
434
84
432
431
75
429
428
430
87
88
91
94
422
96
420
476
419
417
99
415
414
101...

result:

ok q=100000

Test #164:

score: 0
Accepted
time: 39ms
memory: 7152kb

input:

1000 100000
1 13
16 1
17 1
1 22
1 24
29 1
1 30
1 55
57 1
1 58
59 1
1 72
73 1
75 1
77 1
1 85
87 1
1 89
90 1
1 93
1 99
101 1
1 103
1 106
1 119
1 122
125 1
145 1
1 151
1 158
1 163
1 167
170 1
179 1
184 1
1 187
1 193
1 201
202 1
204 1
1 207
1 211
213 1
216 1
222 1
224 1
226 1
234 1
1 242
246 1
259 1
1 2...

output:

2
500
3
4
497
496
6
7
8
9
491
10
489
488
487
486
485
484
483
12
13
15
479
22
477
476
23
30
34
37
38
41
42
43
47
466
48
464
463
51
52
53
459
56
57
58
455
454
453
452
59
450
493
449
61
65
445
444
66
442
441
440
67
438
437
68
435
69
433
432
70
430
28
71
72
73
74
424
75
422
421
77
419
78
417
79
80
81
41...

result:

ok q=100000

Test #165:

score: 0
Accepted
time: 40ms
memory: 7020kb

input:

1000 100000
2 1
3 1
9 1
11 1
22 1
1 33
1 39
1 42
1 43
1 44
1 49
67 1
68 1
73 1
76 1
78 1
81 1
1 84
85 1
87 1
88 1
1 93
1 99
108 1
128 1
1 129
1 132
134 1
135 1
138 1
1 142
144 1
1 150
1 155
158 1
160 1
1 170
1 175
183 1
1 193
1 197
213 1
1 215
216 1
222 1
1 225
1 233
234 1
235 1
242 1
258 1
268 1
1 ...

output:

1
5
499
498
8
496
10
494
13
17
491
490
489
19
20
21
22
25
26
482
481
27
479
29
477
33
475
474
35
472
471
470
36
38
467
41
42
43
47
50
51
56
459
486
64
66
67
454
453
69
451
70
71
72
73
74
445
444
443
442
441
440
76
78
437
436
435
79
433
80
431
430
84
428
427
426
86
88
89
422
94
95
99
100
417
416
101
...

result:

ok q=100000

Test #166:

score: 0
Accepted
time: 37ms
memory: 6956kb

input:

1000 100000
13 1
22 1
1 24
1 29
32 1
42 1
46 1
50 1
1 56
1 62
66 1
1 68
1 69
71 1
1 73
1 75
81 1
1 87
88 1
94 1
1 96
101 1
107 1
1 108
110 1
111 1
126 1
1 143
148 1
1 150
160 1
166 1
176 1
1 180
1 183
1 195
1 206
211 1
1 213
1 216
219 1
236 1
1 238
1 242
1 249
251 1
252 1
256 1
266 1
1 277
1 293
295...

output:

7
500
499
9
497
496
495
14
493
492
491
15
489
17
487
19
485
21
483
482
22
23
479
478
25
476
27
474
473
28
29
470
469
468
467
466
465
30
463
462
32
33
35
458
37
38
455
454
43
452
451
450
46
47
447
446
51
444
443
442
55
56
58
61
437
436
435
62
63
64
431
65
66
68
427
426
70
424
73
74
75
77
419
78
79
81...

result:

ok q=100000

Test #167:

score: 0
Accepted
time: 26ms
memory: 7152kb

input:

1000 100000
1 4
1 7
8 1
14 1
16 1
1 17
20 1
22 1
1 28
1 29
34 1
1 35
1 38
1 41
1 49
1 53
1 57
1 58
1 74
1 84
85 1
1 90
95 1
103 1
104 1
1 107
108 1
110 1
1 117
1 118
1 126
1 141
142 1
1 145
1 147
1 152
153 1
154 1
1 163
1 165
166 1
173 1
175 1
180 1
1 184
188 1
1 189
194 1
201 1
204 1
207 1
1 210
21...

output:

1

result:

ok q=100000

Test #168:

score: 0
Accepted
time: 34ms
memory: 6972kb

input:

1000 100000
15 1
18 1
1 26
31 1
1 37
1 40
42 1
1 46
1 48
1 49
1 53
55 1
1 68
75 1
82 1
83 1
89 1
92 1
102 1
106 1
1 113
1 114
1 119
1 121
1 123
128 1
129 1
130 1
1 133
140 1
1 143
1 153
1 154
1 163
1 167
168 1
171 1
176 1
178 1
1 190
191 1
1 192
1 200
201 1
204 1
205 1
1 206
212 1
1 215
1 218
1 223
...

output:

185
22
23
45
49
65
88
89
107
492
92
490
491
137
72
40
46
144
149
156
159
59
123
119
133
162
30
71
87
95
146
126
1
82
15
469
155
481
12
85
173
460
143
110
20
52
455
73
47
34
461
489
44
471
51
101
457
19
443
452
127
440
129
497
54
58
96
102
106
432
462
430
429
428
427
426
14
424
21
448
421
484
454
61
...

result:

ok q=100000

Test #169:

score: 0
Accepted
time: 31ms
memory: 7036kb

input:

1000 100000
5 1
14 1
1 17
33 1
40 1
55 1
1 58
59 1
1 61
1 66
70 1
1 71
1 75
76 1
79 1
1 81
90 1
95 1
1 102
1 104
1 109
119 1
130 1
1 131
142 1
144 1
147 1
1 154
158 1
1 161
170 1
178 1
1 182
187 1
189 1
1 211
217 1
1 229
1 233
245 1
248 1
1 249
254 1
256 1
1 257
258 1
271 1
1 273
1 277
286 1
1 287
1...

output:

0
0
16
44
129
193
231
61
270
305
77
312
314
173
283
209
4
323
329
163
498
184
206
271
355
83
93
180
220
60
47
472
471
42
130
165
237
258
281
284
325
328
343
360
388
495
48
99
396
156
453
171
368
3
449
7
13
39
54
492
476
35
111
167
182
103
474
436
18
56
88
124
160
262
63
279
452
50
425
424
423
95
440...

result:

ok q=100000

Test #170:

score: 0
Accepted
time: 37ms
memory: 7048kb

input:

1000 100000
1 5
1 13
1 19
26 1
1 29
34 1
35 1
38 1
39 1
45 1
1 46
1 67
79 1
1 92
94 1
1 97
108 1
1 111
1 120
122 1
1 129
131 1
140 1
1 143
148 1
159 1
1 169
175 1
180 1
185 1
187 1
1 189
1 192
1 195
200 1
205 1
1 208
1 213
1 228
1 232
243 1
244 1
1 245
1 246
1 263
271 1
274 1
1 281
292 1
299 1
301 1...

output:

0
75
208
39
294
378
112
317
69
425
457
309
119
491
526
584
522
277
421
675
167
234
106
238
267
477
513
646
403
621
705
711
724
260
470
790
806
834
851
852
869
877
906
181
585
909
632
672
136
827
870
919
1021
1031
1039
1045
1497
1046
1072
1086
1098
1110
217
614
153
412
484
616
52
244
298
33
126
211
2...

result:

ok q=100000

Test #171:

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

input:

1000 100000
1 3
4 1
1 5
8 1
1 11
1 21
1 24
1 27
36 1
45 1
1 51
1 74
1 75
79 1
1 80
83 1
1 86
1 93
1 95
98 1
101 1
106 1
109 1
110 1
117 1
127 1
1 130
1 131
1 137
1 141
145 1
1 154
155 1
160 1
1 164
166 1
168 1
169 1
172 1
1 173
174 1
181 1
1 185
1 188
198 1
1 202
1 212
217 1
1 228
230 1
1 234
1 235
...

output:

0
0
1393
2599
561
125
500
143
216
405
733
887
944
973
196
1166
704
169
444
934
18
966
228
1170
1327
1359
1556
1725
624
284
1024
1042
424
992
1192
1443
1619
139
526
907
1267
1756
1858
378
90
1051
1252
1828
1927
1948
2008
212
787
1370
2500
2499
238
27
430
805
1766
1974
1975
647
316
509
1005
1176
1206
...

result:

ok q=100000

Test #172:

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

input:

1000 100000
4 1
1 6
8 1
1 9
12 1
16 1
1 20
1 32
50 1
1 62
70 1
1 72
1 74
1 77
78 1
1 79
1 84
88 1
89 1
94 1
95 1
1 97
107 1
114 1
1 115
126 1
130 1
132 1
1 138
1 144
1 156
1 162
1 163
165 1
178 1
1 181
1 185
1 192
200 1
214 1
1 215
1 218
1 221
1 226
1 232
1 235
1 237
246 1
1 249
1 256
1 269
279 1
28...

output:

0
0
0
0
0
1357
793
1765
2163
1467
1536
2177
2194
2801
2991
3089
3364
3603
3795
4168
510
715
1099
274
1298
1501
1011
1875
1912
2888
3020
3127
596
1590
1995
1782
2802
3333
3488
349
1141
1734
3378
3707
3873
4309
4362
104
1911
3126
4096
509
782
1165
1573
1754
2709
3184
3578
3975
4094
4161
4281
237
489
5...

result:

ok q=100000

Test #173:

score: 0
Accepted
time: 21ms
memory: 6976kb

input:

1000 100000
4 1
7 1
10 1
1 11
1 15
19 1
20 1
25 1
1 37
40 1
41 1
1 45
1 49
1 55
62 1
67 1
68 1
1 70
1 84
1 87
98 1
102 1
1 122
1 131
141 1
1 148
149 1
1 150
1 155
1 165
1 171
1 179
183 1
185 1
1 189
191 1
1 193
201 1
1 205
217 1
218 1
219 1
1 237
1 240
1 251
257 1
261 1
268 1
274 1
1 285
286 1
1 289...

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 q=100000

Test #174:

score: 0
Accepted
time: 27ms
memory: 7068kb

input:

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

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 q=100000

Test #175:

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

input:

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

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 q=100000

Test #176:

score: 0
Accepted
time: 25ms
memory: 6992kb

input:

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

output:

1
0
500
0
499
0
498
0
497
0
496
0
495
0
494
0
493
0
492
0
491
0
490
0
489
0
488
0
487
0
486
0
485
0
484
0
483
0
482
0
481
0
480
0
479
0
478
0
477
0
476
0
475
0
474
0
473
0
472
0
471
0
470
0
469
0
468
0
467
0
466
0
465
0
464
0
463
0
462
0
461
0
460
0
459
0
458
0
457
0
456
0
455
0
454
0
453
0
452
0
45...

result:

ok q=100000

Test #177:

score: 0
Accepted
time: 26ms
memory: 7136kb

input:

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

output:

0
1
0
500
499
0
0
498
497
496
0
0
495
494
0
493
0
0
492
491
490
489
0
0
488
0
487
0
0
0
0
0
0
486
0
485
484
0
483
482
0
0
481
480
479
478
477
476
0
0
0
0
475
474
473
0
472
471
470
0
469
468
0
0
0
467
466
0
465
0
464
0
463
462
0
461
460
459
0
458
457
456
455
454
453
0
452
0
0
0
0
451
450
449
0
0
448
...

result:

ok q=100000

Test #178:

score: 0
Accepted
time: 19ms
memory: 6972kb

input:

970 100000
2 1
3 1
1 5
1 7
1 9
11 1
1 13
15 1
1 17
19 1
1 21
23 1
1 25
1 27
29 1
31 1
1 33
35 1
37 1
39 1
1 41
1 43
1 45
1 47
1 49
51 1
1 53
55 1
1 57
59 1
61 1
63 1
1 65
67 1
1 69
1 71
73 1
75 1
77 1
79 1
1 81
83 1
1 85
1 87
89 1
91 1
93 1
1 95
1 97
1 99
101 1
1 103
1 105
1 107
1 109
1 111
113 1
11...

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
1
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok q=100000

Test #179:

score: 0
Accepted
time: 21ms
memory: 7132kb

input:

970 100000
2 1
1 3
1 5
7 1
1 9
11 1
13 1
1 15
17 1
1 19
1 21
23 1
1 25
27 1
29 1
31 1
1 33
1 35
1 37
1 39
1 41
1 43
1 45
47 1
1 49
1 51
1 53
55 1
57 1
59 1
61 1
63 1
1 65
1 67
1 69
1 71
1 73
1 75
77 1
79 1
1 81
83 1
1 85
87 1
89 1
1 91
1 93
1 95
97 1
99 1
1 101
1 103
1 105
107 1
109 1
111 1
113 1
1 ...

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 q=100000

Test #180:

score: 0
Accepted
time: 25ms
memory: 7048kb

input:

970 100000
1 2
3 1
1 5
7 1
9 1
11 1
13 1
15 1
17 1
1 19
21 1
1 23
1 25
1 27
1 29
1 31
33 1
35 1
37 1
1 39
1 41
43 1
1 45
1 47
49 1
51 1
1 53
55 1
57 1
1 59
1 61
1 63
65 1
67 1
1 69
1 71
1 73
1 75
1 77
79 1
1 81
1 83
1 85
1 87
89 1
1 91
93 1
95 1
97 1
1 99
1 101
103 1
105 1
107 1
1 109
111 1
1 113
1 ...

output:

1
0
500
0
499
0
498
497
2
0
3
496
4
493
5
0
491
489
6
488
486
485
484
483
482
481
480
0
495
0
479
0
494
477
475
474
492
0
473
471
470
469
490
468
487
0
466
464
463
0
501
462
461
460
502
0
459
458
457
456
503
455
454
0
453
0
504
452
505
0
506
0
451
0
450
449
448
447
446
445
507
0
444
443
508
0
442
44...

result:

ok q=100000

Test #181:

score: 0
Accepted
time: 21ms
memory: 7140kb

input:

970 100000
2 1
3 1
5 1
1 7
9 1
11 1
1 13
15 1
1 17
19 1
21 1
23 1
1 25
1 27
29 1
1 31
1 33
1 35
1 37
39 1
41 1
1 43
45 1
1 47
1 49
51 1
53 1
1 55
1 57
59 1
1 61
63 1
1 65
67 1
69 1
71 1
73 1
75 1
1 77
1 79
1 81
83 1
1 85
87 1
89 1
1 91
1 93
95 1
1 97
1 99
1 101
103 1
105 1
107 1
1 109
111 1
113 1
11...

output:

0
1
2
3
500
497
4
496
5
6
7
494
490
8
0
0
0
0
489
487
0
0
9
0
485
0
486
483
482
481
499
0
480
478
477
498
0
476
474
473
472
471
495
493
492
0
0
0
470
0
466
465
0
0
464
0
0
0
0
0
491
463
461
0
0
0
488
0
0
0
0
501
502
503
504
505
506
507
508
0
0
460
0
509
458
510
511
0
0
512
513
514
515
516
0
457
456
...

result:

ok q=100000

Test #182:

score: 0
Accepted
time: 28ms
memory: 7004kb

input:

970 100000
1 3
4 1
1 10
1 13
16 1
19 1
22 1
1 25
28 1
1 31
34 1
40 1
43 1
58 1
61 1
1 64
70 1
73 1
76 1
82 1
85 1
1 91
94 1
1 100
1 103
1 109
1 112
115 1
118 1
1 127
1 130
1 133
136 1
1 139
142 1
157 1
1 160
1 163
1 166
1 178
1 184
1 187
1 190
193 1
1 196
199 1
1 205
208 1
217 1
1 220
223 1
226 1
1 ...

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 q=100000

Test #183:

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

input:

970 100000
2 1
10 1
13 1
16 1
22 1
25 1
1 28
31 1
1 34
1 37
40 1
1 46
49 1
55 1
70 1
1 76
1 79
1 82
85 1
1 88
106 1
1 109
1 112
1 115
1 118
124 1
127 1
130 1
1 136
1 139
1 145
1 154
1 157
1 160
163 1
166 1
1 172
1 175
181 1
184 1
193 1
1 196
1 208
211 1
214 1
220 1
223 1
229 1
232 1
1 235
1 238
247 ...

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
1
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 q=100000

Test #184:

score: 0
Accepted
time: 25ms
memory: 7080kb

input:

970 100000
3 1
4 1
1 7
10 1
13 1
16 1
19 1
1 22
1 25
1 28
37 1
1 40
43 1
46 1
1 49
52 1
1 55
1 58
1 64
1 67
1 70
73 1
76 1
79 1
1 85
91 1
94 1
97 1
106 1
1 109
1 112
115 1
1 118
1 124
127 1
133 1
139 1
1 142
1 148
1 154
157 1
160 1
1 163
166 1
169 1
172 1
175 1
181 1
1 184
187 1
1 190
1 193
199 1
1 ...

output:

1
0
210
0
211
0
500
497
496
0
2
3
495
4
212
5
213
492
487
486
485
0
6
7
8
9
10
11
484
477
12
13
14
0
15
0
16
476
17
0
18
19
20
470
465
0
214
0
215
0
216
21
464
22
23
24
217
25
218
26
27
0
219
459
449
28
448
446
445
444
29
30
31
0
32
443
438
437
220
0
33
34
436
432
431
0
430
429
221
0
222
428
223
425...

result:

ok q=100000

Test #185:

score: 0
Accepted
time: 26ms
memory: 6988kb

input:

970 100000
1 2
1 4
1 7
10 1
1 13
16 1
1 19
1 22
1 25
28 1
1 37
49 1
1 52
1 55
1 67
1 70
1 73
79 1
85 1
1 88
1 91
1 94
1 97
1 100
103 1
1 106
112 1
118 1
124 1
1 133
1 136
139 1
142 1
145 1
1 154
160 1
1 163
1 172
1 175
178 1
181 1
184 1
193 1
1 196
199 1
1 205
208 1
211 1
1 220
223 1
232 1
1 235
238...

output:

1
211
212
213
214
215
216
2
3
4
5
500
489
488
487
486
0
0
0
6
485
483
482
481
480
217
218
0
0
7
8
9
219
220
479
471
470
469
468
467
466
221
465
463
462
0
222
461
459
458
457
456
455
454
453
10
11
12
223
224
452
225
226
0
13
14
15
16
17
18
446
437
436
435
434
433
432
431
430
429
428
427
19
227
20
21
...

result:

ok q=100000

Test #186:

score: 0
Accepted
time: 25ms
memory: 7080kb

input:

970 100000
3 1
5 1
1 9
13 1
17 1
21 1
29 1
1 33
1 37
1 41
1 49
53 1
57 1
69 1
1 73
1 77
1 81
85 1
1 89
93 1
97 1
1 101
1 105
1 117
121 1
125 1
1 129
133 1
137 1
141 1
1 145
1 149
153 1
157 1
1 161
169 1
1 173
1 181
185 1
189 1
193 1
1 197
201 1
209 1
213 1
217 1
1 221
225 1
229 1
1 233
241 1
1 245
2...

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 q=100000

Test #187:

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

input:

970 100000
1 3
1 4
5 1
9 1
13 1
17 1
1 21
25 1
29 1
33 1
1 37
1 49
1 53
1 57
61 1
65 1
69 1
1 73
81 1
1 85
89 1
1 105
1 113
1 117
1 121
1 125
129 1
133 1
1 137
141 1
1 145
149 1
153 1
1 157
1 161
1 165
1 189
1 193
197 1
201 1
1 205
209 1
1 213
1 217
221 1
225 1
229 1
237 1
1 241
1 245
1 249
1 253
26...

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
210
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 q=100000

Test #188:

score: 0
Accepted
time: 22ms
memory: 7048kb

input:

970 100000
2 1
1 3
4 1
1 5
1 9
1 13
17 1
1 21
1 25
33 1
1 37
41 1
1 45
49 1
57 1
61 1
1 65
69 1
1 73
81 1
1 85
1 89
1 97
1 101
105 1
1 113
1 117
1 121
125 1
1 129
133 1
137 1
1 141
149 1
153 1
1 157
1 161
1 165
169 1
1 173
1 177
1 181
185 1
189 1
197 1
1 201
205 1
1 209
1 213
217 1
1 221
1 229
233 1...

output:

1
0
3
0
2
500
497
496
495
494
493
0
492
491
627
212
628
4
490
487
5
0
629
6
7
213
8
486
480
479
478
477
476
214
215
475
472
471
470
469
468
467
466
216
9
465
462
461
460
459
458
457
456
455
454
453
452
10
11
0
12
13
217
0
218
451
444
443
630
219
442
440
439
438
437
436
435
434
433
432
431
430
429
42...

result:

ok q=100000

Test #189:

score: 0
Accepted
time: 22ms
memory: 7020kb

input:

970 100000
2 1
1 3
4 1
1 5
1 9
13 1
1 17
1 21
1 33
1 37
1 41
45 1
49 1
53 1
57 1
1 61
1 65
1 69
73 1
1 77
1 81
85 1
1 89
1 93
97 1
1 101
105 1
1 109
1 117
1 121
125 1
1 129
137 1
1 141
145 1
1 149
1 153
161 1
1 169
1 173
1 177
181 1
1 185
1 189
1 193
197 1
1 201
205 1
1 209
213 1
217 1
1 229
233 1
2...

output:

3
1
2
4
499
496
627
628
5
6
7
8
9
10
495
488
487
486
485
484
483
482
481
480
479
478
477
476
475
474
473
472
471
629
630
470
469
631
632
468
467
466
465
464
463
633
210
211
212
213
462
457
456
455
454
453
452
451
450
449
448
447
446
445
444
443
442
441
440
439
438
214
634
215
437
434
433
432
216
431...

result:

ok q=100000

Test #190:

score: 0
Accepted
time: 28ms
memory: 6816kb

input:

970 93610
1 3
1 4
1 6
1 11
16 1
21 1
1 26
1 31
36 1
1 41
46 1
1 51
56 1
1 61
1 66
1 71
76 1
81 1
86 1
1 91
96 1
101 1
106 1
1 111
1 116
121 1
126 1
1 131
136 1
141 1
1 146
1 151
1 156
161 1
1 166
171 1
176 1
181 1
186 1
1 191
1 196
1 201
1 206
211 1
216 1
1 221
1 226
1 231
236 1
241 1
246 1
1 251
1 ...

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 q=100000

Test #191:

score: 0
Accepted
time: 26ms
memory: 6776kb

input:

970 93610
5 1
6 1
1 11
16 1
1 21
26 1
1 31
36 1
41 1
46 1
1 51
56 1
1 61
1 66
1 71
1 76
81 1
86 1
1 91
96 1
1 101
106 1
1 111
1 116
121 1
1 126
1 131
1 136
1 141
146 1
1 151
1 156
161 1
1 166
1 171
176 1
1 181
1 186
1 191
196 1
1 201
1 206
1 211
1 216
1 221
226 1
1 231
236 1
1 241
1 246
1 251
1 256
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
196
584
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 q=100000

Test #192:

score: 0
Accepted
time: 20ms
memory: 6712kb

input:

970 93610
1 2
1 3
4 1
1 5
6 1
1 11
16 1
21 1
1 26
1 31
1 36
41 1
46 1
1 51
1 56
61 1
1 66
1 71
76 1
1 81
86 1
1 91
1 96
1 101
106 1
111 1
116 1
121 1
1 126
1 131
1 136
141 1
146 1
1 151
156 1
1 161
1 166
171 1
1 176
1 181
186 1
1 191
196 1
201 1
1 206
1 211
1 216
1 221
1 226
231 1
1 236
1 241
246 1
...

output:

2
1
499
498
497
496
495
494
3
199
4
200
493
201
5
202
6
7
8
198
9
10
11
488
477
12
13
14
15
585
476
471
470
469
468
467
466
465
464
463
462
461
460
16
17
18
19
20
21
22
23
24
459
449
203
25
26
204
205
586
778
0
206
207
208
0
27
28
779
209
448
436
435
434
433
432
431
430
429
428
427
426
425
424
423
2...

result:

ok q=100000

Test #193:

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

input:

970 93610
1 3
1 6
1 11
1 16
21 1
26 1
1 31
36 1
41 1
46 1
51 1
1 56
61 1
66 1
1 71
1 76
81 1
1 86
91 1
96 1
1 101
106 1
1 111
116 1
1 121
1 126
1 131
1 136
141 1
146 1
151 1
156 1
1 161
166 1
1 171
1 176
1 181
1 186
1 191
1 196
201 1
1 206
1 211
216 1
221 1
226 1
231 1
1 236
1 241
1 246
1 251
1 256
...

output:

195
1
2
3
4
5
6
499
493
492
196
197
198
199
0
0
0
0
491
486
485
484
483
482
481
480
479
390
585
0
0
7
8
9
10
11
12
13
478
469
468
467
466
465
14
15
200
391
778
779
780
781
16
17
464
457
456
455
454
453
452
451
450
449
448
201
202
203
18
19
20
21
22
23
24
447
436
204
25
26
27
28
29
30
435
427
426
425...

result:

ok q=100000

Test #194:

score: 0
Accepted
time: 17ms
memory: 6288kb

input:

970 77288
1 2
3 1
1 4
5 1
1 7
13 1
1 19
1 25
31 1
37 1
43 1
1 49
1 55
61 1
1 67
1 73
1 79
1 85
91 1
97 1
103 1
1 109
115 1
121 1
1 127
133 1
139 1
1 145
1 151
1 157
1 163
169 1
175 1
181 1
187 1
193 1
199 1
205 1
1 211
217 1
1 223
1 229
1 235
241 1
1 247
253 1
259 1
1 265
271 1
1 277
1 283
289 1
1 2...

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
3
165
487
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 q=100000

Test #195:

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

input:

970 77288
1 2
5 1
1 6
7 1
13 1
19 1
1 25
31 1
37 1
43 1
49 1
55 1
61 1
1 67
1 73
1 79
1 85
91 1
1 97
103 1
109 1
115 1
1 121
127 1
1 133
139 1
145 1
151 1
157 1
1 163
1 169
175 1
1 181
1 187
1 193
199 1
1 205
1 211
1 217
223 1
1 229
235 1
1 241
1 247
253 1
1 259
1 265
1 271
1 283
289 1
295 1
301 1
1...

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
164
326
327
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
2
487
0
0
0
0
0
0
1
165
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok q=100000

Test #196:

score: 0
Accepted
time: 20ms
memory: 6192kb

input:

970 77288
2 1
1 5
1 6
1 7
1 13
1 19
1 25
1 31
37 1
43 1
1 49
1 55
61 1
67 1
73 1
79 1
1 85
91 1
97 1
103 1
109 1
1 115
1 121
127 1
133 1
139 1
145 1
1 151
157 1
1 163
169 1
175 1
1 181
187 1
1 193
199 1
1 205
1 211
1 217
223 1
229 1
235 1
1 241
247 1
253 1
1 259
265 1
271 1
277 1
1 283
1 289
295 1
3...

output:

164
1
327
2
499
496
165
166
167
168
648
328
649
0
495
489
488
497
486
3
487
169
170
650
483
480
479
478
477
476
475
474
808
4
5
473
470
469
468
467
466
465
464
463
462
461
460
171
172
6
173
651
7
8
9
10
11
12
13
652
809
653
14
654
500
494
493
492
491
15
16
17
459
438
437
436
435
434
433
432
431
18
1...

result:

ok q=100000

Test #197:

score: 0
Accepted
time: 21ms
memory: 6336kb

input:

970 77288
2 1
1 4
1 5
1 7
13 1
1 25
31 1
37 1
43 1
1 49
1 55
61 1
67 1
73 1
1 79
1 85
1 91
97 1
1 103
1 109
1 115
121 1
127 1
1 133
1 139
1 145
1 151
1 157
163 1
169 1
175 1
1 181
1 187
193 1
199 1
1 205
211 1
1 217
223 1
229 1
235 1
1 241
1 247
1 253
1 259
1 265
1 271
1 277
283 1
1 289
295 1
301 1
...

output:

1
2
3
4
161
162
163
164
5
6
7
8
9
10
11
12
13
14
15
16
481
480
479
482
477
644
645
0
0
500
499
498
497
492
491
490
489
488
17
487
486
485
484
483
165
166
475
458
457
456
455
454
453
452
451
450
449
448
447
18
19
446
443
442
441
440
439
438
437
20
21
22
23
24
25
26
27
496
495
28
29
30
31
436
421
420
...

result:

ok q=100000

Test #198:

score: 0
Accepted
time: 20ms
memory: 5748kb

input:

970 66182
2 1
1 3
4 1
1 6
7 1
1 8
15 1
1 22
1 29
36 1
43 1
50 1
1 57
1 64
1 71
1 85
1 92
99 1
1 106
113 1
1 120
1 127
1 134
1 141
148 1
155 1
162 1
1 169
1 176
1 183
190 1
1 197
204 1
1 218
225 1
232 1
239 1
246 1
1 253
1 260
1 267
1 274
281 1
1 288
1 295
302 1
1 309
316 1
323 1
1 330
337 1
1 344
1 ...

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
140
557
0
0
0
0
0
4
141
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 q=100000

Test #199:

score: 0
Accepted
time: 21ms
memory: 5728kb

input:

970 66182
1 4
5 1
1 6
7 1
8 1
15 1
1 22
29 1
36 1
43 1
1 50
1 57
1 64
71 1
1 78
1 85
92 1
1 99
1 106
1 113
1 120
127 1
134 1
1 141
1 148
1 155
162 1
1 169
1 176
183 1
1 190
197 1
1 204
211 1
1 218
1 225
232 1
239 1
246 1
253 1
260 1
267 1
274 1
281 1
288 1
295 1
1 302
309 1
1 316
1 323
330 1
337 1
3...

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
2
144
56...

result:

ok q=100000

Test #200:

score: 0
Accepted
time: 11ms
memory: 5648kb

input:

970 66182
1 2
1 5
1 7
8 1
1 15
22 1
1 29
1 36
43 1
1 57
64 1
1 71
1 78
85 1
1 92
1 99
106 1
1 113
1 120
1 127
134 1
141 1
148 1
155 1
1 162
1 169
1 176
1 183
1 190
197 1
204 1
211 1
1 218
225 1
232 1
1 239
1 246
253 1
260 1
267 1
274 1
281 1
1 288
295 1
1 302
1 309
316 1
1 323
1 330
1 337
344 1
351 ...

output:

278
3
141
279
2
281
1
494
493
4
5
6
140
418
492
486
485
484
483
482
481
480
479
478
477
476
475
474
473
7
8
9
472
468
467
466
465
464
463
10
462
460
459
458
457
456
455
454
453
11
280
12
558
142
13
14
15
16
17
18
282
419
833
559
452
439
438
437
436
435
434
433
432
283
431
429
428
427
426
425
284
424...

result:

ok q=100000

Test #201:

score: 0
Accepted
time: 15ms
memory: 5748kb

input:

970 66182
4 1
1 5
6 1
1 8
15 1
1 22
1 29
1 36
43 1
1 50
1 57
1 64
1 71
78 1
85 1
92 1
1 99
106 1
1 113
120 1
1 127
134 1
1 141
148 1
155 1
162 1
169 1
1 176
183 1
1 190
197 1
204 1
1 211
1 218
225 1
232 1
1 239
1 246
1 253
1 260
267 1
274 1
1 281
288 1
295 1
302 1
309 1
316 1
323 1
330 1
337 1
344 1...

output:

0
142
2
1
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
144
24
498
474
473
472
471
470
469
468
467
466
465
464
463
462
461
460
25
26
27
28
29
143
459
452
451
450
449
448
447
446
445
444
443
145
146
147
148
149
150
151
152
153
30
31
32
33
154
155
281
283
282
417
442
422
421
418
557
695
420
...

result:

ok q=100000

Test #202:

score: 0
Accepted
time: 18ms
memory: 5552kb

input:

970 58094
3 1
1 4
1 5
1 7
8 1
1 9
17 1
1 25
33 1
1 41
49 1
1 57
1 65
73 1
81 1
1 89
97 1
105 1
113 1
1 121
1 129
137 1
145 1
153 1
161 1
169 1
1 177
1 185
193 1
1 201
1 209
1 217
1 225
233 1
1 241
249 1
1 257
265 1
273 1
1 281
1 289
297 1
1 305
1 313
321 1
329 1
1 337
1 345
1 353
1 361
369 1
1 377
1...

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
248
610
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 q=100000

Test #203:

score: 0
Accepted
time: 11ms
memory: 5568kb

input:

970 58094
3 1
5 1
1 9
17 1
25 1
33 1
1 41
49 1
57 1
1 65
1 73
1 81
1 89
1 97
105 1
1 113
121 1
1 129
137 1
1 145
1 153
1 161
1 169
1 177
1 185
193 1
1 201
209 1
217 1
225 1
233 1
1 241
1 249
1 257
1 265
1 273
1 281
289 1
297 1
305 1
313 1
1 321
329 1
1 337
1 345
353 1
1 361
1 369
1 377
1 385
1 393
4...

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
1
2
0
0
0
0
0
125
249
371
493
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
124
494
248
0
0
0
0
0
0
0
...

result:

ok q=100000

Test #204:

score: 0
Accepted
time: 13ms
memory: 5420kb

input:

970 58094
2 1
5 1
1 6
7 1
1 8
1 9
17 1
25 1
1 33
41 1
1 49
1 57
1 65
1 73
1 81
89 1
97 1
1 105
113 1
1 121
1 129
137 1
1 145
1 153
1 161
1 169
1 177
1 185
193 1
1 201
209 1
217 1
1 225
233 1
241 1
1 249
257 1
265 1
273 1
1 281
1 289
297 1
305 1
1 313
321 1
329 1
337 1
345 1
1 353
1 361
369 1
377 1
1...

output:

1
2
4
3
127
249
500
494
129
128
130
5
489
488
487
493
499
497
498
496
485
480
479
478
477
476
475
474
473
472
471
470
469
468
6
467
465
464
463
462
7
131
8
461
457
456
455
454
453
452
451
450
449
448
447
446
445
444
443
442
132
492
495
250
251
9
441
434
433
432
431
430
429
428
133
10
11
12
13
14
15
...

result:

ok q=100000

Test #205:

score: 0
Accepted
time: 10ms
memory: 5436kb

input:

970 58094
4 1
5 1
7 1
8 1
9 1
1 17
1 25
33 1
41 1
1 49
1 57
1 65
1 73
81 1
89 1
1 97
1 105
113 1
121 1
129 1
1 137
1 145
153 1
1 161
1 169
1 177
1 185
1 193
201 1
209 1
217 1
225 1
233 1
241 1
249 1
257 1
265 1
1 273
1 281
1 289
297 1
1 305
313 1
1 321
1 329
1 337
1 345
1 353
1 361
1 369
377 1
385 1...

output:

0
126
0
4
130
254
375
2
495
499
1
492
491
490
489
488
487
500
498
252
253
486
481
480
497
255
256
257
258
3
129
259
260
732
733
734
735
736
737
128
738
739
740
5
6
7
8
9
10
11
12
13
14
15
16
479
456
455
454
453
452
451
450
449
448
447
446
445
444
443
442
441
440
439
438
437
436
435
434
433
432
431
4...

result:

ok q=100000

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-02 22:46:46 | OpenSource Project