Farmer John's farm has a very old stone tablet with $n$ positive integers $a_1,a_2,\cdots,a_n$ engraved on it. According to legend, if someone can answer the least common multiple(LCM) of all the integers engraved on it after seeing this stone tablet, the Cowcow God will take him to heaven; otherwise, the Cowcow Ghost will pull him into hell! Unfortulately, Cosmic-Cow accidentally saw this stone tablet while playing, and now she has to answer this problem... In fact, the cow are not brave, she is afraid that she will go to hell if she answers wrong. Please help her! You just need to read out the **prime factorization result** of LCM in front of the stone tablet, in ascending order of prime factor. - Prime Factorization Result: Represent composite number as the multiplication of multiple prime numbers. For example, $24$ can be represented as $2^3\times 3^1$.

The first line contains a positive integer $n$, representing the amount of integers. Next $n$ lines, each line contains a positive integer $a_i$. $1\le n\le 2000$ $2\le a_i\le 10^8$

Output in ascending order of prime factors, with two positive integers per line, representing the prime factors and their powers respectively.