Mr. Vadivu has a decimal chemical. To kill Mr. Kanth, he creates a poison chemical by the following steps.

For example if he has a decimal chemical A: 152

Step 1: He converts it to a binary chemical B (Most significant bit on the left.)

    B: 10011000

Step 2: Then he dilutes it into a poison chemical D such that

For i in 0 to length
    D[i] = D[i-1] + B[i], where D[-1] = 0

In the above case the poison is

    D: 11123333

Mr. Vadivu mixed this poison in Mr. Kanth’s food and Mr. Kanth ate it. After he ate it Mr. Vadivu said to Mr. Kanth, “Ha, you just ate the poison D. If you dont eat the anti-poison A, you will die.”

Assume you are Mr. Kanth and decide whether to die or not to die.

Input

The first line consists of an integer t, denotes the number of test cases.

Next t lines consists of poison chemicals D. (Length of the poison chemical is < 64 and D[i] <= 9.)

Output

For each poison chemical D, print the anti-poison chemical A.

Example

Input:
4
11123333
11122233334444
000000011234555555
1111122222333334444455555

Output:
152
9352
1504
17318416

WARNING: note that the length of the poison chemical is < 64.