# Beam Balance and Masses

Problem #139

Tags: puzzle numeral-system

Who solved this?

Beam Balance is a device for measuring unknown weights by balancing them with a set of known masses. As you may see from the picture above, they were known even in Ancient Egypt more than 3000 years ago.

The device consists of the horizontal beam holding two pans. The object to be measured is placed at one pan and some masses of known weights are collected upon another until the beam will return to horizontal position showing that weights on both pans become equal.

In the case above the object is the heart of a man and the feather of truth is used as a mass. At this scene participants are not interested in the exact weight of the heart but rather try to check whether it is lighter or heavier in comparison to some standard.

### Set of Masses

Most of sets of masses provide standards of the weight based on decimal system, for example:

``````1g  1g  2g  5g  10g 10g 20g 50g
``````

These eight masses allow us to represent any weight up to `99` grams. Of course you may say that if we use binary system, less masses are needed:

``````1g  2g  4g  8g  16g  32g  64g
``````

Here are only `7` instead of `8` and they allow to represent weights up to `127` grams! Can we reduce the number of masses further?

Yes, we can! Because we can place some smaller masses onto the pan with the weighed object, effectively subtracting their weight from other masses. Regard the following set of masses:

``````1g  3g  9g  27g  81g
``````

Suppose the weight to measure equals to `55g`. Then we place masses of `81g` and `1g` onto the free pan and `27g` onto the pan with the object:

``````object + 27g  ==  81g + 1g
``````

So you see, only `5` masses allow to measure weights upto `121` gram.

### Problem statement

Given some weight you are to tell how many masses from this last set should be used to represent it. E.g. `55g` is represented with `3` masses in example above.

You may use any mass equal to some power of `3` (i.e. not limited with `81` but further with `243`, `729` and so on) - though none could be used more than once.

Input data will give a number of test-cases in the first line.
Next line will contain test-cases - each with a single value - the weight to represent - not exceeding `2 000 000 000` grams.
Answer should contain the amount of masses used for each weight.

Example:

``````input data:
17
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85

``````5   ==   9 - 3 - 1