Description

As we all know, data is stored in computers in binary form.
After learning about binary conversion, a student wants to try it out himself. Given a non-negative integer $x$, he wants to convert it to binary. Can you help him solve this problem?

Input Format

The first line contains an integer $t$ ($2≤t≤1000$).
The next $t$ lines each contain a number $x$ ($1≤x≤10^8$), which is a non-negative integer.

Output Format

$t$ lines, each containing a binary string representing the binary form of each $x$. (No leading zeros)

Sample

4
1
2
3
4

1
10
11
100