|
I I U P C 2 0 1 3 |
|
|
Problem E: Little Rakin |
|
|
|
|
|
Little Rakin is learning Math. While learning the Fibonacci series, he is talking over the phone to his paternal aunt who lives in New York. The Fibonacci series is:
F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 , n > 1
But Rakin, who is listening to the visit that his uncle’s family paid in the statue of Liberty on the phone, became very fascinated. He begins to imagine himself on the place, forgetting his present state. Due to his loss in concentration, what Rakin writes is:
F0 = 0 F1 = 1 Fn = Fn-1 × Fn-2 , n > 1
Now, you have to solve a problem which is similar to ‘Little Rakin’s Fibonacci series’. Here is a sequence given:
F0 = a F1 = b Fn = Fn-1 × Fn-2 , n > 1
Given a, b, and n, prime factorize Fn.
|
|
|
Input |
|
|
First line of the input will consist of the number of test cases T ≤ 100. Then T cases follows. For each case, there is a line containing three number n, a, b, where : 2 ≤ n ≤ 40 2 ≤ a, b ≤ 1000
|
|
|
Output |
|
|
Print the prime factorization of Fn so that each prime number and its power will be in a single line separated by single space. If there is more than one prime, then prime numbers should be printed in increasing order. Print a blank line after each test case. For more clarification see the sample output format given below.
|
|
|
Sample Input |
Output for the Sample Input |
|
2 2 2 3 13 2 3
|
2 1 3 1
2 144 3 233
|
|
|
|
|
Problem Setter : Mohammad Hafiz Uddin Alternate Solution : Md. Amjad Hossain Rahat |
|