#2348. 迷宫

迷宫

迷宫

题目描述

3 迷宫 3.1 题目描述 九条可怜是一个贪玩的女孩子。 暑假快要到了,可怜打算在她家的私人海滩旁边建一座城堡,这样就可以在放暑假的时候 邀请她的朋友们来玩了。同时,可怜打算在城堡的地下修建一座迷宫,因为探险总是一件充满 乐趣的事情。 经过简单的设计,可怜打算修建一座这样的迷宫: • 迷宫可以被抽象成n 个点,nm 条边的有向图。1 号点是唯一的入口也是唯一的出口。 • 每一个点恰好有m 条出边,且这些出边被依次标号为[0, m) 的正整数。 • 迷宫允许自环和重边。 同时,一座优秀的迷宫应该有一定的解谜因素。因此可怜希望每一条从1 号点出发并回到 1 号点的回路都有着一定的规律。 可怜发现,如果把一条从1 出发的路径经过的所有边的编号都记录下来,那么能得到一个 (可能有前导0)的m 进制数;同时对于每一个(可能有前导0)的m 进制数,都能对应回一 条从1 出发的路径。 于是可怜选定了一个整数K,她希望这个迷宫满足一条从1 出发的路径能回到1 当且仅当 这条路径对应的数是K 的倍数。 现在可怜已经选定了m 和K,但是她发现并不是对所有的n,都存在满足上述所有条件的 迷宫设计方案。建造迷宫是一件费时费力的事情,于是可怜想要找到一个最小的满足条件的n。 然而可怜对复杂的计算并不感兴趣,因此她想让你来帮她计算一下这个数值。 3.2 输入Ḑᓣ 第一行输入一个整数T 表示数据组数。 接下来T 行每行两个十进制正整数m, K 表示可怜选定的整数。 3.3 输出Ḑᓣ 对于每组数据,输出一行一个整数表示能够满足所有条件的最小的n。如果不存在这样的 n,输出−1。 3.4 样例输入 3 2 3 6

2 4 6 8 3.5 样例输出 3 3 5 3.6 样例解䞞 第一组数据(左)和第二组数据(右)的一种设计方案如下图所示。其中紫色边表示0 号 边,蓝色边表示1 号边。 3.7 数据㣗ೈ与约定 测试点 m K t 其他约定 1 ≤6 ≤10 ≤100 无 2 ≤100 ≤100 3 4 ≤105 ≤105 5 6 ≤109 ≤109 ≤1000 m 为质数 7 无 8 9 ≤1018 ≤1018 ≤3 × 105 10 对于100% 的数据,保证m ≥2。 7

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
2 3
2 4
6 8
3
3
5

样例 2

200
40 39
93 4
60 93
54 20
42 74
81 2
26 89
58 96
17 76
63 61
84 80
92 42
44 20
17 90
97 92
28 61
12 33
16 16
39 68
21 45
88 42
66 99
62 19
5 72
94 46
11 66
97 96
12 13
2 36
21 53
27 4
42 93
50 82
53 87
100 60
85 12
56 5
34 57
20 15
60 21
50 12
44 29
58 99
94 88
82 45
7 53
19 70
59 29
5 3
70 43
68 15
20 76
98 96
42 57
11 4
43 34
52 29
30 30
63 61
55 15
25 62
4 81
42 26
55 63
50 80
40 32
33 39
6 47
59 23
22 11
88 66
36 49
62 27
68 13
75 36
66 26
95 39
34 52
28 24
28 36
9 50
89 67
75 73
31 62
14 26
66 44
39 59
41 33
2 44
44 69
48 11
19 58
17 52
100 34
47 75
42 65
83 8
88 17
63 39
67 39
234 547296750
15 191291100
42 533709000
800 212576400
320 134217728
500 468468000
300 18918900
42 26952750
162 967458816
1188 40310784
70 668918250
162 830513250
486 349920000
1428 328703760
27 564350976
660 615882960
260 343543200
1728 816293376
45 27000000
252 429556050
1664 964689920
126 85995000
864 668860416
45 255150000
336 874800000
1078 181252500
700 963144000
156 270270000
405 841802544
126 839368530
1760 765164400
1620 612220032
720 806215680
240 648000000
315 585585000
490 297675000
120 417704625
225 975975000
150 437400000
270 388800000
20 645918000
520 598152555
192 301989888
312 61661600
1152 712800000
720 526500000
900 425250000
48 806215680
150 216090000
384 325058560
162 790272000
882 348625200
360 885487680
150 570810240
600 611226000
180 342286560
640 268435456
1815 336174300
576 626102400
126 400207500
816 465567744
3136 838860800
624 342641664
128 603979776
1512 895795200
54 564350976
3264 302330880
6624 524040192
576 436207616
5120 503316480
512 855638016
1188 537477120
912 453496320
528 589545216
1215 443418624
384 436207616
3200 536870912
128 603979776
1600 436207616
1632 80621568
63 359995323
15 431493186
54 269664375
25 693497755
89 629532992
16 870498324
2 64756751
39 396957418
14 396306805
71 318296480
38 630736373
20 166524085
97 806022014
52 23889638
40 191040749
60 168757288
43 775718441
90 969776572
23 323658606
88 185001164
39
4
32
11
38
2
89
49
76
61
21
22
6
90
92
61
12
2
68
13
22
4
19
72
24
7
96
13
11
53
4
32
42
87
4
12
5
57
4
8
7
29
99
45
45
53
70
29
3
43
15
20
49
20
4
34
29
2
61
4
62
81
14
63
9
5
14
47
23
2
4
49
27
13
13
14
39
27
7
10
50
67
73
3
14
3
59
33
13
69
11
58
52
18
75
65
8
17
14
39
10329
2550550
824025
531442
164
117244
7109
167853
1036
165
382255
189877
16590
6962
28675
25978
2544
91
595
69650
643
8130
31
125
95457
4119425
358
48140
332
951667
173904
49
35
36
18906
3667
371366
104135
116
246
322962
9202348
8
148229
34377
1487
10
275
2479
168
5547788
6081
102489
91344
7795
26418
157
4239
1630479
75627
38773
5651
12576
13
857
927
12109
904
846
10
54
1413
33186
49860
22534
53
907
13
2315
1036
119998442
143831063
89888126
138699552
629532992
217624582
64756751
30535187
396306805
318296480
630736373
33304818
806022014
11944820
191040749
21094677
775718441
242444189
323658606
46250292