package Lanqiao_test01;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class HexadecimalToOctal {
	
	public static void main(String[] args) throws Exception{
		
		System.out.println("请按输入格式输入:");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 第一行: 行个数
		
		String[] str = new String[n];
		for(int i=0; i<str.length; ++i){
			str[i] = br.readLine();
		}
		
		
		for(int j=0; j<n; ++j){
			transform1(str[j]);
		}
		
	}
	
	
	/*	transform1: 将输入的十六进制转化为二进制
	 * 	1. 将十六进制字符串转化为字符数组c1
	 *  2. 将单个十六进制字符转化为二进制数(1位16进制 对应 4位二进制) 用sb接收
	* */
	public static void transform1(String s1){
		char[] c1 = new char[s1.length()];
		c1 = s1.toCharArray();
		StringBuffer sb = new StringBuffer();
		
		for(int i=0; i<c1.length; ++i){
			switch(c1[i]){
			case '0':
				sb.append("0000");
				break;
			case '1':
				sb.append("0001");
				break;
			case '2':
				sb.append("0010");
				break;
			case '3':
				sb.append("0011");
				break;
			case '4':
				sb.append("0100");
				break;
			case '5':
				sb.append("0101");
				break;
			case '6':
				sb.append("0110");
				break;
			case '7':
				sb.append("0111");
				break;
			case '8':
				sb.append("1000");
				break;
			case '9':
				sb.append("1001");
				break;
			case 'A':
				sb.append("1010");
				break;
			case 'B':
				sb.append("1011");
				break;
			case 'C':
				sb.append("1100");
				break;
			case 'D':
				sb.append("1101");
				break;
			case 'E':
				sb.append("1110");
				break;
			case 'F':
				sb.append("1111");
				break;	
			}
		}
		
		transform2(sb);
		
	}
	
	
	/*
	 * transform2: 二进制 转 八进制 并输出结果
	 * 	转换算法: 1.	增补二进制位数,以3位二进制数表示1位八进制数.若长度不合适,进行补0或减0操作
	 * 			2.  对二进制与十进制之间进行转化, 用sb2进行接收
	 * */
	public static void transform2(StringBuffer sb){
	
		int sbLen = sb.length();
		
		if(sbLen % 3 == 0){
			if(sb.substring(0, 3).equals("000"))
				sb.delete(0, 3);
		}
		
		if(sbLen % 3 == 1){
			if(sb.substring(0, 1).equals("0"))
				sb.delete(0, 1);
			else
				sb.insert(0, "00");
		}
		
		if(sbLen % 3 == 2){
			if(sb.substring(0, 2).equals("00"))
				sb.delete(0, 2);
			else
				sb.insert(0, "0");
		}
		
		//001 010 101 ...
		int n = sb.length()/3;

		StringBuffer sb2 = new StringBuffer();
		
		for(int i=0; i<n; i++){
		
			if("000".equals(sb.substring(i*3, i*3+3))) //0,3  3,6   i*3, i*3+3  
				sb2.append("0");
			else if("001".equals(sb.substring(i*3, i*3+3)))
				sb2.append("1");
			else if("010".equals(sb.substring(i*3, i*3+3)))
				sb2.append("2");
			else if("011".equals(sb.substring(i*3, i*3+3)))
				sb2.append("3");
			else if("100".equals(sb.substring(i*3, i*3+3)))
				sb2.append("4");
			else if("101".equals(sb.substring(i*3, i*3+3)))
				sb2.append("5");
			else if("110".equals(sb.substring(i*3, i*3+3)))
				sb2.append("6");
			else if("111".equals(sb.substring(i*3, i*3+3)))
				sb2.append("7");
		
		}
		
		
		System.out.println(sb2);
	}
}