#P4339. [ZJOI2018] 迷宫

    ID: 3288 Type: RemoteJudge 1000ms 500MiB Tried: 0 Accepted: 0 Difficulty: 7 Uploaded By: Tags>数学2018各省省选浙江强连通分量,缩点

[ZJOI2018] 迷宫

题目背景

九条可怜是一个贪玩的女孩子。

题目描述

暑假快要到了,可怜打算在她家的私人海滩旁边建一座城堡,这样就可以在放暑假的时候 邀请她的朋友们来玩了。同时,可怜打算在城堡的地下修建一座迷宫,因为探险总是一件充满 乐趣的事情。

经过简单的设计,可怜打算修建一座这样的迷宫:

  • 迷宫可以被抽象成 nn 个点,nmnm 条边的有向图。11 号点是唯一的入口也是唯一的出口。
  • 每一个点恰好有 mm 条出边,且这些出边被依次标号为 [0,m)[0,m) 的正整数。
  • 迷宫允许自环和重边。

同时,一座优秀的迷宫应该有一定的解谜因素。因此可怜希望每一条从 11 号点出发并回到 11 号点的回路都有着一定的规律。可怜发现,如果把一条从 11 出发的路径经过的所有边的编号都记录下来,那么能得到一个(可能有前导 00)的 mm 进制数;同时对于每一个(可能有前导 00)的 mm 进制数,都能对应回一 条从 11 出发的路径。

于是可怜选定了一个整数 KK,她希望这个迷宫满足一条从 11 出发的路径能回到 11 当且仅当这条路径对应的数是 KK 的倍数。

现在可怜已经选定了 mmKK,但是她发现并不是对所有的 nn,都存在满足上述所有条件的迷宫设计方案。建造迷宫是一件费时费力的事情,于是可怜想要找到一个最小的满足条件的 nn

然而可怜对复杂的计算并不感兴趣,因此她想让你来帮她计算一下这个数值。

输入格式

第一行输入一个整数 TT 表示数据组数。

接下来 TT 行每行两个十进制正整数 m,Km,K 表示可怜选定的整数。

输出格式

对于每组数据,输出一行一个整数表示能够满足所有条件的最小的 nn。如果不存在这样的 nn,输出 -1

3 
2 3
2 4 
6 8
3 
3
5

提示

第一组数据(左)和第二组数据(右)的一种设计方案如下图所示。其中紫色边表示 00 号边,蓝色边表示 11 号边。