Font Size: ← →

Problem Description

任何一个有理数都可以表示成M/N的形式（M,N均为正整数）。例如1/2,2/4,3/6都是等值的有理数。给定若干有理数，等值有理数的值只能算一个，问这些有理数含有多少个值，并按从小到大输出各值及该值的有理数个数。

Input

第一行是整数n,表示随后有n组测试数据（n不超过10）。
每一组测试数据的第一行是一个整数m(m<=100000)，随后有m行，每一行都是A/B的形式, 1<=A,B<=1000000000

Output

对于每一组测试数据，输出要求如下，第一行输出有理数值的个数p，随后的p行按从小到大的次序每一行输出一个A/B形式的值及其对应的有理数个数，用空格分开，要求A/B是最简分数。

Sample Input

2 2 1/3 1/4 4 1/1 1/2 7/14 7/7

Sample Output

2 1/4 1 1/3 1 2 1/2 2 1/1 2

Author

CYH

Source

#include #include #include using namespace std; struct node{ int a; int b; double res; }stu[100000]; int gcd(int a,int b) { int t,r; if(a