SP9723 CODESPTC - Card Shuffling

有一种用来洗 $N$ 张牌的算法，具体步骤如下： 1. 首先，将这 $N$ 张牌平均分成 $K$ 堆，其中 $K$ 是 $N$ 的一个因数。 2. 把最底下的 $N / K$ 张牌按顺序放入第 1 堆，这样，原本牌堆最底下的一张牌就会变成第 1 堆的最下方的牌。 3. 接下来 $N / K$ 张牌从底部开始放入第 2 堆，如此类推，将牌完成分堆。 4. 然后，新的牌堆从顶部往下的第 1 张牌为第 1 堆的顶牌，第 2 张牌为第 2 堆的顶牌，依此类推，第 $K$ 张牌为第 $K$ 堆的顶牌。接下来，第 $(K + 1)$ 张牌就是现在第 1 堆的顶牌，第 $(K + 2)$ 张牌就是现在第 2 堆的顶牌，如此下去。 比如，当 $N = 6$ 且 $K = 3$ 时，原本牌堆的排列是 "ABCDEF"（从顶到底），洗一次后变为 "ECAFDB"。 给定 $N$ 和 $K$，请问至少需要多少次洗牌才能使牌堆恢复到最初的顺序？

第一行输入一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行中，每行包含两个整数 $N$ 和 $K$。

输出 $T$ 行，每行对应一个测试用例的结果，表示最少需要的洗牌次数。如果牌堆永远无法恢复成原来的顺序，输出 -1。 ## 数据范围 $$1 \le T \le 100, \quad 1 \le N \le 10^5, \quad 1 \le K \le N, \quad K \text{ 是 } N \text{ 的因数}。$$ **本翻译由 AI 自动生成**