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
israt_123: 2023-09-22 08:01:48

why runtime error.???????????????????????

tracyyi: 2022-06-10 08:34:33

How can I get the test data of a problem?

kumaarbalbir: 2021-08-15 16:17:07

make sure you print Case instead of case in your answer!!

sankalp_7: 2021-06-24 08:18:54

Simple spf question.

ratkill: 2021-05-23 20:40:02

The code runs fine on my machine but wrong answer when i compile the code.

princemishra: 2020-10-26 14:33:58

remember to format the output as ----
Case i: factors

fuadul_hasan: 2020-06-26 09:00:41

at last AC
..

fuadul_hasan: 2020-06-26 03:58:00

why runtime error............?

rofiqul: 2019-08-02 07:48:44

i donot know why i get runtime error

ujjwalmittal: 2019-07-07 13:42:39

easy AC in one go but i used sieve


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