Дано \(n\) цілих чисел \(a_1, a_2, \dots a_n\).

Нехай число \(A\) рівне добутку \(a_1 \cdot a_2 \cdot \dots \cdot a_n\).

Знайдіть факторизацію числа \(A\).

Input Specification

У першому рядку вхідного файлу задано ціле число \(n\) \((1 \le n \le 10^5)\).

У другому рядку розміщено \(n\) цілих чисел - послідовність \(a\) \((1\le a_i \le 10^5)\).

Output Specification

У першому рядку виведіть одне число \(k\) - кількість простих дільників числа \(A\).

У кожному з наступних \(k\) рядків виведіть два числа - \(p_i\) та \(\alpha_i\), такі, що всі \(p_i\) є простими та \(p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dots \cdot p_k^{\alpha_k} = A\).

Числа повинні бути виведені у порядку зростання \(p_i\).

Sample Input 1

1
18

Sample Output 1

2
2 1
3 2

Sample Input 2

4
45 13 1 34

Sample Output 2

5
2 1
3 2
5 1
13 1
17 1