巨大乘积的指数形式

题目描述

给定 m 个整数，分别分解质因数，并将相同质因数的指数累加，得到全部整数乘积的质因数指数形式。总乘积可能超出 64 位范围，不得先计算乘积。

输入格式

第一行输入 m，满足 1≤m≤100。第二行输入 m 个整数 ai，满足 2≤ai≤10^9。

输出格式

每行输出总乘积中的一个质因数 p 及总指数 e，按 p 从小到大排列。

样例

输入

1
12

输出

2 2
3 1