Hệ thập phân (cơ số 10) là hệ cơ số mà con người chúng ta sử dụng hàng ngày trong cuộc sống. Thế nhưng, chiếc máy tính của chúng ta lại chỉ có thể làm việc với hệ nhị phân (cơ số 2).

Ví dụ:

• ~8_{10} = 1000_{2} = 1*2^3 + 0*2^2 + 0*2^1 + 0*2^0~

Yêu cầu:

Cho một số nguyên dương trong hệ cơ số ~10~, hãy viết số đó trong hệ cơ số ~2~ (hệ nhị phân).

Input

• Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ trong hệ thập phân.

Giới hạn:

• ~1 ≤ T ≤ 10^5, 1 ≤ n ≤ 10^{18}~

Output

• Với mỗi số nguyên dương ~n~ trong hệ thập phân, in ra trên một dòng xâu nhị phân biểu diễn số đó trong hệ nhị phân (không bắt đầu bởi số ~0~).

Sample

Input #1

3
5
7
10

Output #1

101
111
1010

Problem source: Chuyên Sơn La Online Judge