505029 - 阶的分类

【题目描述】阶的分类（classification）

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

第一行一个整数t（1≤t≤10），表示测试组数。 随后t行：每行一个数p（1≤p≤10^9）为质数。

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

【样例说明】 对于3，阶为1的只有1，阶为2的只有2。 对于5，阶为1的只有1，阶为2的只有4，阶为4的包括2，3，其中2是最小的。