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

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 xâu nhị phân (số được biểu diễn trong hệ nhị phân).

Giới hạn:

• ~1≤T≤10^5~. Độ dài mỗi xâu nhị phân không quá ~63~

Output

• Với mỗi xâu nhị phân, in ra trên một dòng số đó trong hệ thập lục phân (Các ký tự A.. F viết hoa).

Sample

Input #1

3
101
111
1010

Output #1

5
7
A

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