QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#267891#7735. Primitive Rootucup-team984AC ✓24ms3700kbC++17528b2023-11-27 20:24:542024-04-08 18:17:22

詳細信息

Test #1:

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

input:

3
2 0
7 11
1145141 998244353

output:

1
2
872

result:

ok 3 lines

Test #2:

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

input:

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

output:

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

result:

ok 47595 lines

Test #3:

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

input:

100000
11 34
71 35
11 45
53 28
3 67
17 38
41 2
23 8
47 26
79 98
89 47
97 33
43 95
97 98
29 79
29 48
67 27
37 3
97 72
71 97
67 53
23 77
71 12
101 92
89 63
61 71
59 94
97 2
29 64
53 74
47 78
67 0
97 66
79 81
3 48
67 87
79 88
59 63
17 25
61 37
67 64
79 93
67 92
89 0
59 88
11 29
29 5
13 47
101 80
3 12
8...

output:

3
1
5
1
23
3
1
0
0
2
1
1
2
2
4
3
1
1
1
2
1
4
0
1
1
3
3
1
3
2
2
0
1
2
16
2
2
2
2
1
1
2
2
0
3
3
1
4
1
4
1
1
14
45
1
1
3
1
4
2
1
2
1
1
2
1
8
2
1
2
1
1
0
1
2
2
1
3
3
9
1
2
1
1
32
1
1
2
1
1
0
1
4
1
1
3
1
2
1
2
2
1
0
2
3
0
1
1
1
3
2
2
1
5
4
1
1
3
2
0
3
2
3
1
6
1
2
9
0
2
2
3
1
1
2
1
2
2
1
1
0
2
2
12
21
4
3...

result:

ok 100000 lines

Test #4:

score: 0
Accepted
time: 7ms
memory: 3696kb

input:

100000
29 83
47 14
29 56
2 29
17 35
67 31
3 24
97 39
17 5
59 16
53 51
29 51
67 72
53 14
79 54
11 35
83 56
89 11
5 70
67 42
89 65
7 40
41 45
79 13
7 26
5 51
5 49
47 46
19 2
89 74
47 27
71 37
37 39
83 86
7 86
71 15
29 94
19 17
101 56
23 3
59 95
97 73
11 15
29 66
23 23
23 51
53 95
11 95
61 0
97 14
73 5...

output:

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

result:

ok 100000 lines

Test #5:

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

input:

100000
59 60
97 9
53 69
7 58
71 67
3 88
61 92
83 42
67 64
71 43
29 30
83 31
89 89
47 93
67 90
97 74
11 80
89 84
47 38
19 43
67 55
59 15
101 68
71 58
97 40
73 94
71 88
89 8
67 35
37 81
31 24
23 58
73 51
43 34
71 88
41 69
37 37
7 2
79 79
97 65
17 89
41 78
31 3
97 37
7 91
47 95
97 33
97 60
37 74
29 83
...

output:

2
1
2
8
1
29
3
1
1
1
2
1
2
2
2
1
8
1
1
3
1
1
1
1
1
2
2
1
1
2
0
3
1
1
2
2
2
0
2
1
6
2
0
1
14
2
1
1
2
4
5
0
5
1
2
1
1
1
0
1
1
0
7
17
2
7
3
1
0
0
1
1
8
3
1
2
1
1
1
1
0
1
1
7
4
2
7
5
0
1
21
3
1
1
0
3
0
0
2
1
1
1
2
5
6
4
1
2
1
1
2
1
4
1
1
2
21
0
3
1
5
1
20
1
2
1
3
5
0
0
6
3
1
2
5
0
1
3
8
2
1
3
1
1
3
1
1
...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 12ms
memory: 3624kb

input:

100000
1861 3528
2333 9090
2579 5653
8147 4315
1381 1926
1213 8598
7681 7742
5039 8270
7927 3661
2819 9458
7229 4213
683 8300
787 4660
7753 1678
7283 9943
6029 2737
5051 6439
9371 9827
1277 5268
2753 5913
5437 1537
2851 4021
1289 1807
6529 7605
7949 9316
8101 2770
6451 2437
2039 1348
1307 6586
9011 ...

output:

3
4
3
1
2
8
2
2
1
3
1
13
7
1
3
1
2
2
4
2
1
2
2
2
3
1
1
1
5
1
2
1
1
1
1
14
6
4
1
1
1
2
1
1
2
23
1
32
1
2
7
4
1
2
3
1
2
2
4
1
9
1
4
3
4
1
5
3
2
2
4
123
1
2
9
1
1
3
1
1
2
1
3
1
1
4
3
1
1
1
1
1
1
1
1
3
1
1
4
4
1
3
1
18
1
11
1
2
2
1
3
1
1
0
329
1
1
2
3
1
2
1
1
4
1
1
2
4
5
1
3
1
7
2
1
1
2
1
2
2
2
1
1
1
2
...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 12ms
memory: 3628kb

input:

100000
2861 7238
2411 6690
1951 8793
7877 4503
7237 6677
8311 2550
9883 8304
233 2207
9397 6356
907 7980
7591 192
7643 9101
8963 3945
5683 436
6007 4005
3299 123
1103 5136
9719 9329
2099 1890
7793 6195
2203 8339
4057 9237
5521 3288
6733 7011
563 5121
2879 8277
9091 124
1913 229
307 7781
1801 7702
67...

output:

2
3
6
1
1
1
1
9
1
9
1
2
1
1
1
1
5
1
1
1
4
4
1
2
10
3
1
1
27
5
1
5
1
2
3
2
1
1
22
2
2
1
1
2
1
1
1
1
1
2
1
1
1
4
1
1
18
1
4
11
42
1
3
2
1
2
2
2
1
1
6
1
2
1
1
3
1
1
13
35
1
1
1
1
1
1
3
2
1
1
1
1
7
1
1
1
5
1
1
2
3
1
1
1
1
2
1
1
5
1
4
6
2
1
51
1
1
8
4
3
13
31
5
2
1
50
1
2
1
1
3
19
1
1
2
13
3
1
1
3
1
2
1
...

result:

ok 100000 lines

Test #8:

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

input:

100000
7177 7208
2753 1599
2909 8176
6547 7781
2543 4318
7177 3366
127 1355
7283 479
6073 6686
3847 195
6761 3446
2099 2392
2609 4676
3637 3268
8849 7603
5179 7731
827 7446
3163 299
9461 8223
6581 8750
4373 9228
9187 8667
2963 6819
4057 7322
5059 9167
9041 3320
9151 8842
2153 6137
1993 6329
4517 606...

output:

2
1
3
2
2
1
12
1
2
1
1
2
2
1
1
2
9
1
1
2
3
1
2
3
2
1
1
3
4
2
2
1
2
1
2
16
1
5
1
1
40
1
1
1
1
30
1
3
2
1
3
3
2
2
4
10
2
9
1
2
1
1
2
1
3
1
1
1
6
2
1
1
2
4
3
1
1
2
1
1
2
2
1
1
2
2
3
1
1
1
1
6
1
2
3
1
6
1
1
2
1
1
1
1
5
2
1
2
2
5
1
3
1
2
2
1
3
47
7
4
1
1
2
1
3
1
1
3
2
2
7
18
1
1
1
1
1
2
5
3
2
1
1
1
1
3
1...

result:

ok 100000 lines

Test #9:

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

input:

100000
22957699 627925429
433183259 202804355
816810829 985631258
54563549 847625650
712837669 860468289
452708161 516705387
541041323 722654987
456499961 122097506
110566411 638241209
103870223 415782860
591063689 459421060
851704643 560244670
491675827 960606500
724808879 813870033
513057607 82205...

output:

27
1
2
15
2
2
2
1
6
5
1
1
3
2
3
4
1
4
1
1
1
1
14
2
1
4
1
1
1
1
1
1
1
1
1
2
2
1
3
1
31
1
1
11
10
1
2
1
1
1
1
1
1
1
2
3
1
1
1
3
2
2
1
3
7
3
1
5
4
2
1
1
2
3
2
1
1
6
2
3
2
1
3
4
2
1
2
3
1
1
2
1
20
1
1
10
9
12
1
1
1
1
1
2
1
1
1
3
2
98
2
1
1
3
1
1
2
7
2
1
1
1
6
1
2
1
1
4
2
1
1
2
1
6
1
1
3
3
2
3
2
1
2
1
1
...

result:

ok 100000 lines

Test #10:

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

input:

100000
821384891 360483232
94753013 575184250
387876647 758829597
792132637 476022188
535607833 726268124
410858009 781602681
205636231 376470383
645933731 695016569
300304427 613786984
973582219 833018963
29026219 535160021
635806387 1063241
345979391 601446921
785258833 658427991
90922421 44784451...

output:

1
7
2
1
3
3
3
2
3
1
19
1
2
1
5
3
1
1
7
1
2
1
1
10
1
2
2
2
2
1
15
5
1
1
2
1
1
14
1
2
2
1
1
6
1
10
1
3
1
2
1
4
9
1
4
1
1
3
1
582
1
1
1
3
1
5
1
2
2
6
3
2
1
2
1
3
1
1
6
8
1
1
1
3
1
2
1
1
1
1
8
4
2
1
1
1
2
1
1
5
1
1
3
2
1
2
1
2
3
2
1
5
1
1
1
1
1
1
3
1
1
1
2
5
1
1
2
3
1
1
2
1
3
1
1
1
5
1
2
2
1
1
12
1
2
4
...

result:

ok 100000 lines

Test #11:

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

input:

100000
461078399 442550442
375521033 166102087
604976747 331845816
889534567 570960171
535876871 139282340
31131031 344924738
847344217 802184255
28753481 655216151
866254967 928501728
688120403 888670298
877525879 756867078
356855867 761054248
447231371 477259710
294217477 234719004
964538831 66564...

output:

1
1
1
1
1
11
1
24
2
2
1
3
2
1
1
1
3
7
1
2
1
1
1
1
1
2
3
8
1
1
1
2
2
2
1
1
1
2
4
1
1
1
2
3
9
1
1
1
3
1
5
1
2
4
2
4
1
2
2
2
1
5
1
3
2
4
3
1
1
4
1
1
7
1
1
1
2
1
1
1
1
8
1
3
1
1
2
2
1
3
1
2
1
1
85
1
1
1
2
6
9
3
1
1
2
1
1
1
2
2
4
3
2
2
10
1
1
1
1
3
1
16
12
12
1
2
1
1
6
2
2
6
3
1
1
1
1
2
2
2
1
1
2
1
1
1
2...

result:

ok 100000 lines

Test #12:

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

input:

100000
854620121447 305351081320
465821420627 871311229833
798238974037 704593959229
82347058499 514594072052
78827529281 752873405762
666400710491 526552474252
437289823799 509968252445
301446931481 962983709877
33747912293 818002585949
538211581429 511798563550
750166805383 54533573983
17865394271...

output:

1
3
1
7
10
1
2
4
25
1
1
1
2
2
1
1
1
17
3
2
2
5
3
3
1
5
1
1
7
3
7
3
1
2
1
4
3
2
1
19
3
3
2
1
2
6
7
2
1
2
1
1
1
1
1
1
1
3
2
1
5
1
1
2
2
2
18
1
1
5
1
8
4
1
7
1
2
1
2
17
1
9
2
1
3
2
1
1
4
2
1
2
2
1
3
1
1
1
1
4
1
2
1
10
1
2
1
2
1
4
2
5
1
2
1
1
1
2
1
1
4
27
2
1
2
1
1
27
2
5
2
1
40
1
7
2
1
3
3
3
2
3
1
1
1
...

result:

ok 100000 lines

Test #13:

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

input:

100000
653643377183 209815203180
360818541247 201512061317
10499747803 884463867404
393797197091 234742176386
703806710617 249134196381
907111880249 117784843971
7251683917 175985067098
942415308949 620757896798
100232848427 681361142924
910954687609 667339222842
458654023019 976379522216
7578431335...

output:

1
1
85
1
1
1
24
1
7
1
3
2
1
3
2
1
1
1
1
3
3
2
2
1
1
2
2
20
2
1
1
2
1
8
2
1
5
1
6
2
5
1
1
1
1
3
2
2
1
2
1
3
2
11
9
1
1
1
5
3
2
2
8
9
1
4
1
1
1
1
2
3
28
1
1
1
1
1
1
3
2
1
1
1
2
1
6
1
1
7
6
3
2
2
1
1
3
1
1
4
2
2
1
1
2
7
1
1
2
1
3
2
2
2
2
1
2
1
1
23
2
2
2
2
1
1
15
1
1
1
1
3
2
1
11
1
1
2
1
5
3
3
1
2
7
2
...

result:

ok 100000 lines

Test #14:

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

input:

100000
160125432991 475051983094
819602886679 897389271502
678683084113 569622411514
693327957977 644715715338
934013525429 656254498442
882423180421 325527047003
372238916617 592630991201
103117005307 188247573815
365204005631 992392281776
200101992971 774412000171
535601515147 197520852483
5536176...

output:

3
2
1
1
1
1
2
3
3
5
1
2
1
1
1
1
1
8
1
1
1
2
1
1
2
1
5
2
1
1
3
1
2
7
1
9
1
3
3
2
2
12
2
1
1
4
2
1
1
1
1
1
1
15
3
1
2
12
1
1
1
1
10
2
2
2
1
2
1
2
1
1
1
2
2
2
1
2
2
1
1
4
3
1
1
1
3
2
1
1
1
1
3
1
2
2
2
1
7
4
1
1
11
1
1
1
2
2
1
2
1
1
1
1
6
4
2
1
1
3
1
1
1
27
2
1
3
1
2
3
5
1
1
1
4
1
15
3
1
17
1
1
1
2
1
1
...

result:

ok 100000 lines

Test #15:

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

input:

100000
359573421097243 33190899500761
429648865238321 111363421683870
423566282667481 76657156109745
944266025027653 53041192687688
5998863263257 461695895601001
971991064370477 903661079717039
342748954516301 175753203478899
969093155697031 62220628919394
249136757321579 631609060170143
43919020024...

output:

1
1
1
1
78
1
1
1
3
1
1
2
1
1
1
1
1
3
78
2
59
1
1
1
1
1
2
8
1
1
1
1
8
2
4
1
2
1
1
1
1
1
5
13
4
2
2
9
1
1
1
1
1
1
2
1
1
3
4
2
2
2
1
1
1
2
3
26
1
40
1
1
7
1
6
2
1
6
2
1
8
1
2
1
27
1
2
2
1
2
1
1
2
2
1
3
1
1
1
1
3
1
1
3
6
4
1
3
1
2
6
7
4
1
1
2
1
1
1
3
1
2
2
1
3
1
9
8
4
1
4
6
1
3
1
5
9
1
3
1
2
32
1
1
2
1
...

result:

ok 100000 lines

Test #16:

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

input:

100000
612187772343991 307898682692355
491563915829227 81876689946461
903496097449081 724223585724217
76596192680681 445610736133832
925209166638019 109668900359025
814982598334559 890952377847942
420890856837109 909991705384765
837583370312123 640461094892448
128215851458909 989991000111952
2749157...

output:

1
1
1
6
1
2
2
1
8
3
1
1
1
2
1
2
1
2
2
3
1
1
2
1
1
1
1
3
1
1
3
3
37
1
5
1
1
2
3
2
1
2
4
1
1
1
6
1
1
1
2
3
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
4
2
1
2
1
2
4
3
4
3
4
2
1
1
1
1
2
2
1
2
4
3
2
8
15
5
4
3
1
9
2
11
1
1
4
1
1
23
2
1
1
1
3
2
1
2
3
11
1
2
2
3
1
3
2
3
1
3
3
1
1
1
1
1
1
1
1
2
2
1
3
1
1
3
10
...

result:

ok 100000 lines

Test #17:

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

input:

100000
527124440985647 595225963083624
878596655176477 267226061229273
511171190874121 539928663112537
708545136837443 572815828041949
508401279002521 728325253245656
958545656352461 208380424460329
630023561631221 900531251759032
856499920764841 620217829008445
664762951245641 992776043426244
88970...

output:

2
1
2
1
3
1
2
1
2
2
1
1
6
5
3
2
7
3
2
12
1
11
17
2
1
4
3
1
1
2
1
1
2
1
2
1
2
2
11
11
5
1
1
1
1
3
1
5
2
2
1
1
1
1
3
8
3
1
1
1
1
1
1
1
1
3
9
1
2
1
24
1
2
3
1
2
3
1
5
1
5
3
2
1
2
1
1
5
2
1
1
2
1
1
2
1
1
2
1
1
1
21
103
1
7
1
3
4
1
2
1
6
2
5
1
8
2
1
1
1
5
1
2
1
2
2
10
2
2
6
1
3
2
2
2
4
1
12
1
8
3
1
4
2
1...

result:

ok 100000 lines

Test #18:

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

input:

100000
137194177351851223 9263960501321274
603695491118374607 404857914356622914
905092930616434199 438619277423348461
225047845117473823 419275192757332987
46077386124583379 58196483892837680
932311941721013233 86830145501282437
428893034875113157 259980893024457722
422564472614618221 4922670871717...

output:

1
1
1
3
2
1
1
2
2
1
1
1
41
1
3
1
1
2
1
2
1
4
8
1
1
5
1
1
1
1
1
2
2
6
1
1
1
2
4
8
3
1
2
1
1
3
1
3
2
1
1
1
2
1
2
1
12
4
4
4
7
1
1
1
1
2
1
2
3
1
5
2
1
1
1
15
2
1
10
1
1
2
1
11
1
2
2
1
1
1
1
4
3
4
1
1
1
4
1
1
2
1
1
10
1
1
2
1
1
2
1
2
3
3
6
1
1
2
1
1
2
1
1
2
2
9
2
1
1
2
2
1
2
3
3
1
1
8
2
1
3
1
6
1
2
1
1
...

result:

ok 100000 lines

Test #19:

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

input:

100000
372459024313481957 706690631540644317
672619818396391 605929237970266041
734983024134395923 404465032880967062
123776024960508211 704655167670475038
694637366930170487 911014424969381821
257826433671775237 32194576516953788
570154615804186159 25699638879637358
86963512790531387 93830733506415...

output:

2
901
1
6
2
1
1
2
1
1
5
1
1
1
1
1
2
2
1
2
1
1
3
3
1
1
3
1
1
18
1
1
5
2
2
1
17
1
1
5
1
2
11
2
5
2
2
1
2
3
10
2
4
1
1
1
1
3
1
2
5
7
4
1
2
1
5
1
6
1
2
3
1
1
1
3
1
2
3
3
4
1
1
1
1
1
4
5
8
3
2
2
3
1
2
7
1
2
2
2
2
2
1
1
2
1
2
13
1
26
1
1
1
1
44
5
4
2
1
4
1
1
2
4
1
1
1
1
1
1
1
1
1
3
1
7
1
2
3
2
2
9
1
5
1
1...

result:

ok 100000 lines

Test #20:

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

input:

100000
966374481426333653 927674754000046276
547619405950404283 459594617974285439
73136580880950767 785269891461922620
297236243166644039 754400221344316960
281874052063114529 682203169755139173
211070435933793739 534953075257260374
186603053201695927 585053341246251851
19587519457672171 4373347880...

output:

1
1
11
3
4
3
4
24
2
6
2
2
2
1
1
7
1
1
3
1
1
2
2
1
3
3
3
2
10
2
3
3
1
4
1
3
2
1
1
1
2
2
3
4
1
2
2
3
1
1
1
3
1
2
7
2
2
1
5
1
1
2
1
2
2
3
1
6
2
2
1
16
2
1
2
4
1
3
2
1
5
5
2
1
1
1
1
3
2
10
1
1
1
5
2
4
1
26
1
1
2
5
6
4
1
4
1
1
1
1
3
1
2
1
1
3
1
2
4
1
1
2
3
1
1
1
1
2
2
2
2
2
1
1
2
1
1
3
1
4
1
1
3
1
1
2
4
...

result:

ok 100000 lines

Extra Test:

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

伺服器時間: 2024-12-05 07:01:42 | 開源專案