Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

#### Problem Description

When transmitting data by network it is important to pack it efficiently since this allows to optimize bandwidth usage. We will describe a decoding procedure in one efficient way of packing integer numbers. It uses variable length and has prefix property to ensure correct decoding. Your task will be to implemen the optimal encoding method.

The method is applicable for transmitting integer numbers from −2^{63 }to 2^{63}− 1 (long type in Java).

Packed integer occupies from 1 to 9 bytes, depending on its value.

Decoding is performed in the following way. First the leading byte of the number is received. Looking at its bits from higher to lower, find the first zero. Let q be the number of these leading ones (if the first byte is 0xff, q = 8). q means the number of bytes to follow. If q = 8, these eight bytes are a standard big-endian (higher byte first) representation of an integer number.

In the other case the following operation is performed: if the q + 2-nd bit of the first byte is zero (bits are numbered from 1, higher bits first, if q = 7, the highest bit of the second byte is considered), leading ones of the first byte are replaced by zeroes, and the number is padded on the left by zero bytes to eight bytes.

In the other case, the q + 1-st bit (it is always zero) is replaced with one, and the number is padded on the left with 0xff bytes to eight bytes. The result is a standard big-endian representation of an integer number.

Given several integer number, you must encode each of them so that the length of the encoded number were minimal possible and it decoded to the original number.

#### Input

The first line of the input file contains n — the number of test cases (1 ≤ n ≤ 10 000). The following n lines contain one number between −2^{63 }and 2^{63}− 1, inclusive, each.

#### Output

Output n lines, each line must contain an encoded version of the corresponding number written as the sequence of hexadecimal digits, higher bytes first.

#### Sample Input

9
0
1
2
3
100
500
1000000
-1
-100

#### Sample Output

00
01
02
03
8064
81f4
cf4240
7f
bf9c

#### Source

Andrew Stankevich Contest 23

#### Manager