BREAKING - Number Breaking


Every number is multiplication of some prime numbers. Prime number is a number which is only divided by 1 and itself. Here you are given a number n. You have to find the prime numbers whose multiplication makes this number.

For example, 12 is multiplication of prime numbers 2 and 3. 15 is multiplication of 3 and 5.

Input

First Line will contain the number of test cases T. Then each line will contain a single integer n.

Constraints: 1≤T≤1000, 2≤n≤1000000.

Output

For each test case print a single line which contains test case number and the prime numbers in ascending order separated by a single space whose multiplication make this number.

Example

Input:
3
12
42
84 Output: Case 1: 2 3
Case 2: 2 3 7
Case 3: 2 3 7
 

hide comments
nishant_26: 2018-01-16 15:12:31

easy! AC in one go

dangerous321: 2017-07-01 19:41:18

what is output if input is prime

losmi247: 2017-06-09 17:24:16

Good basic problem, AC in one go!

Md Jahidul Hasan: 2017-06-09 05:49:05

@bnzhaxx.. try to understand the problem clearly!!

Shubham Jadhav: 2017-05-14 20:21:19

Piece Of Cake..

bnzhaxx: 2017-04-24 23:37:28

LOL 2*3 is 6, not 12

Reayz: 2017-03-09 19:22:46

good one...

Md Jahidul Hasan: 2017-03-09 05:21:49

A Very Good Basic Problem.

Last edit: 2017-03-09 05:22:10

Added by:Shakil
Date:2017-03-09
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All