Biểu diễn nhị phân

Cho \(T\) số tự nhiên. Với mỗi số \(n\), hãy in ra biểu diễn nhị phân của \(n\) (không có chữ số \(0\) thừa ở đầu; với \(n = 0\) in 0).

Gợi ý: biểu diễn nhị phân của \(n\) bằng biểu diễn nhị phân của \(\lfloor n/2 \rfloor\) viết thêm chữ số \(n \bmod 2\) vào cuối. Hãy viết một hàm đệ quy dựa trên nhận xét này.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 1000\)).
• \(T\) dòng tiếp theo, mỗi dòng chứa một số tự nhiên \(n\) (\(0 \le n \le 10^{18}\)).

Output

• In ra \(T\) dòng, mỗi dòng là biểu diễn nhị phân của số tương ứng.

Sample Input 1

3
13
0
8

Sample Output 1

1101
0
1000