B. Asia区域制

单测试点时限: 1.0 秒

内存限制: 512 MB

二进制数据是用 0 和 1 两个数码来表示的数.它的基数为 2 ，进位规则是“逢二进一”，借位规则是“借一当二”，由18世纪德国数理哲学大师莱布尼兹发现.
十六进制（简写为hex或下标 16 ）在数学中是一种逢 16 进 1 的进位制.一般用数字 0 到 9 和字母 A 到 F（或 a ~ f ）表示，其中: a ~ f 表示 10 ~ 15 ，这些称作十六进制数字.
请将给定的二进制数转为十六进制数，英文字母使用小写形式.

输入

第一行一个正整数 T， 代表有 T 组测试数据. (1≤T≤10).
接下来 T 行，每行输入一串只包含 0 和 1 的字符串（无前导 0），字符串长度：1≤length≤106.

输出

对于每组测试样例，输出转化后的十六进制数并单独占一行.

样例

input

2
1
10

output

1
2

二进制转换十六进制的方法：

位数补够4的倍数，每四位转一位；

例如：100101 ，一共6位，先在左端补0，补够8位，变成0010,0101(逗号是为了方便看)

0010 —> 2   , 0101 —>5,十六进制表示就是25

#include<iostream>
#include<algorithm>
using namespace std;  
typedef long long ll;
string ex(string s){
	int n=s.length()%4;
	string ans;
        reverse(s.begin(),s.end());  //反转字符串
        if(n){                //补0
    	    n=4-n;
            while(n--){
    	    s+='0';
	    }
	}
	reverse(s.begin(),s.end());  //再次反转，这样就相当于在前面补够了0
	int m=s.length();
	for(int i=0;i<=m-4;i+=4){
		string b=s.substr(i,4);   
		int t=(s[i]-'0')*2*2*2+(s[i+1]-'0')*2*2+(s[i+2]-'0')*2+(s[i+3]-'0');
	if(t<10) ans+=(t+'0');  //t就是转化为的16进制数字
	else if(t==10) ans+='a';
	else if(t==11) ans+='b';
	else if(t==12) ans+='c';
	else if(t==13) ans+='d';
	else if(t==14) ans+='e';
	else if(t==15) ans+='f';
	}
	return ans;
}
int main(){
	int n;
	cin>>n;
	while(n--){
		string s;
		cin>>s;
		cout<<ex(s)<<endl;
	}
	return 0;
}