3092 -- Non-divisible 2-3 Power Sums

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Language:

Non-divisible 2-3 Power Sums

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1123		Accepted: 524		Special Judge

Description

Every positive integer N can be written in at least one way as a sum of terms of the form (2^a)(3^b) where no term in the sum exactly divides any other term in the sum. For example:

1 = (2⁰)(3⁰)
7 = (2²)(3⁰) + (2⁰)(3¹)
31 = (2⁴)(3⁰) + (2⁰)(3²) + (2¹)(3¹) = (2²) + (3³)

Note from the example of 31 that the representation is not unique.

Write a program which takes as input a positive integer N and outputs a representation of N as a sum of terms of the form (2^a)(3^b).

Input

The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.

Each dataset consists of a single line of input containing a single integer N (1 ≤ N < 2³¹), which is the number to be represented as a sum of terms of the form (2^a)(3^b).

Output

For each dataset, the output will be a single line consisting of: The dataset number, a single space, the number of terms in your sum as a decimal integer followed by a single space followed by representations of the terms in the form [<2 exponent>,<3 exponent>] with terms separated by a single space. <2 exponent> is the power of 2 in the term and <3 exponent> is the power of 3 in the term.

Sample Input

Sample Output

1 1 [0,0]
2 2 [2,0] [0,1]
3 3 [4,0] [0,2] [1,1]
4 1 [5,5]
5 1 [0,12]
6 8 [3,13] [4,12] [2,15] [7,8] [9,6] [0,16] [10,5] [15,2]

Source

Greater New York 2006

[Submit] [Go Back] [Status] [Discuss]

Home Page Go Back To top