Egyptian Fractions

1000ms    65536K
287    73
Difficult

Description

During the Middle Kingdom of Egypt (circa 2000 BC), the Egyptians developed a novel way of writing fractions. Adding a certain symbol to the hieroglyph for an integer was understood to represent the reciprocal of that integer. This made it easy to write any fraction of the form \({1 \over N}\)(called a unit fraction)—simply add the reciprocal symbol to the hieroglyph for N.

There was no direct way to represent a fraction of the form \({M \over N}\), where M > 1. Instead, any such fraction was written as the sum of unit fractions.

Your job is to take a fraction \({M \over N}\) and write it as a sum of unit fractions in the 'best' form. Less fraction item is better. If two expressions has same number of fractions, the smallest fraction larger is better.

For example, the fraction \({3 \over 4}\) could be written as:

\({3 \over 4} = {1 \over 3} + {1 \over 4} + {1 \over 6}\\ {3 \over 4} = {1 \over 2} + {1 \over 4}\)

The last one is the best form.

The fraction \({19 \over 45}\) could be written as:

\({19 \over 45} = {1 \over 3} + {1 \over 12} + {1 \over 180}\\ {19 \over 45} = {1 \over 3} + {1 \over 15} + {1 \over 45}\\ {19 \over 45} = {1 \over 3} + {1 \over 18} + {1 \over 30}\\ {19 \over 45} = {1 \over 4} + {1 \over 6} + {1 \over 180}\\ {19 \over 45} = {1 \over 5} + {1 \over 6} + {1 \over 18}\)

The last one is the best form.

Input

The first line of input contain one integer K, means that there are K test cases.

Following K lines, each line contain two integers M,N (0<M<N<1000)

Output

For each input fraction \({M \over N}\) you are to ouput a single line containing numbers \({D_1 < D_2 < D_3 < ...}\) such that:

\( {M \over N} = {1 \over D_1} + {1 \over D_2} + {1 \over D_3} + ...\)

 

Sample Input

1
19 45

Sample Output

5 6 18

Source

Editor

keefo on 2014-05-11 10:10:08


North University of China

OnlineJudge

NUC

NOJ

OJ

ACM/ICPC