批量整理分数

题目描述

给定 n 个正分数，按输入顺序分别约成最简分数。各个分数相互独立。

输入格式

第一行输入 n，满足 1≤n≤100。接下来 n 行每行输入分子 a、分母 b，满足 1≤a,b≤10^18。

输出格式

输出 n 行，每行依次为对应分数的最简分子和最简分母。

样例

输入

1
6 8

输出

3 4