505028 - 原根

【题目描述】原根(root)

给定一个整数n,求它的所有原根。 为了减小输出量,给出输出参数d,设n的所有原根有c 个,从小到大分别为g1,…,gc,你只需要依次输出gd,g2d,…,g⌊c/d⌋×d。

输入

第一行为一个整数T(1≤T≤10),表示测试数据组数。 接下来T行,每行两个整数n和d(2≤n≤10^6,1≤d≤200),表示一组询问数据。

输出

对于每组数据: 第一行输出一个整数c,表示n的原根个数,第二行输出⌊c/d⌋个数,按照题目描述中要求输出,保证输出的数的总个数不超过10^5。 注意:即使⌊c/d⌋=0,也需要输出一个空行。

样例

输入

6
2 1
4 1
25 2
36 1
9 6
18 1

输出

1
1 
1
3 
8
3 12 17 23 
0
  
2

2
5 11

提示

【样例说明】 对于第1,2,4,6组数据,给出的n的所有原根都出现在输出中。 对于第3组数据,25的原根集合为{2,3,8,12,13,17,22,23}。 对于第5组数据,9的原根集合为{2,5}。

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题