求助站外题（数论）

【题目描述】阶的分类（classification） 给出一个质数p，对1到p-1的数，按照数模p的阶进行分类，求每个分类中最小的数是多少？这里1的阶被认为是1而不是0。

【输入格式】 第一行一个整数t（1≤t≤10），表示测试组数。 随后t行：每行一个数p（1≤p≤1e9）为质数。

【输出格式】 输出共t行，每行按照阶从小到大，输出阶以及最小的数。

已经发现的结论是，所有合法的阶必为p-1的因数。

现在问题转化成了，已知x mod m的阶为t，如何快速求解最小的x。