In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of October 11th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #01 exercise sheet]

[AED004] Bart's Math Problem

Bart Simpson is in trouble again. Mrs. Krabappel has given him math homework, and this time it's serious: prime factorization. While Bart would rather be skateboarding, watching Krusty, or pulling pranks on Principal Skinner, he knows he has to get it done or risk detention.

The task seems simple: given a list of numbers, Bart must break each of them down into their prime factors. But Bart is tired and distracted, so he’s asking you to help him out.

The Problem

Given a list of integers, output the prime factorization of each number in the list.

Input

The first line contains a single integer N, the number of integers in the list.

The second line contains N space-separated integers a_i, .

Output

The output should contain N lines, one for each number in the list.

Each line should be in the format ai=p1*p2*...*pk where pj are the prime factors of the number in increasing order. There should be no spaces between the symbols.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

4
6 630 100 13

6=2*3
630=2*3*3*5*7
100=2*2*5*5
13=13