package com.liuzhen.systemExe;

import java.util.Scanner;

public class Main {

    //把16进制字符串转成2进制字符串

    public String getSixteenToTwo(String A){

        StringBuilder result = new StringBuilder("");

        char[] arrayA = A.toCharArray();

        for(int i = 0;i < arrayA.length;i++){

            int temp;

            if(arrayA[i] >= 'A' && arrayA[i] <= 'F'){

                temp = arrayA[i] - 'A' + 10;

            }

            else

                temp = arrayA[i] - '0';

            result.append(getNumberToTwo(temp));

        }

        String result1 = result.toString();

        return result1;

    }

    //把一个数字0~15转换成4位2进制

    public String getNumberToTwo(int n){

        StringBuilder result = new StringBuilder("");

        for(int i = 0;i < 4;i++){

            int temp = n%2;

            result.append(temp);

            n = n/2;

        }

        String temp1 = result.toString();

        temp1 = getReverseString(temp1);

        return temp1;

    }

    //把2进制字符串转成8进制字符串

    public String getTwoToEight(String A){

        if(A.length() % 3 == 1)

            A = "00" + A;

        if(A.length() % 3 == 2)

            A = "0" + A;

        char[] arrayA = A.toCharArray();

        StringBuilder result = new StringBuilder("");

        int count = 0;

        int tempResult = 0;

        for(int i = arrayA.length-1;i >= 0;i--){

                int temp = arrayA[i] - '0';

                tempResult += (int) (temp*Math.pow(2, count++));

                if(count == 3){

                    count = 0;

                    result.append(tempResult);

                    tempResult = 0;

                }

        }

        String result1 = result.toString();

        result1 = getReverseString(result1);

        result1 = getNonoZeroString(result1);

        return result1;

    }

    //反转字符串

    public String getReverseString(String A){

        char[] arrayA = A.toCharArray();

        int start = 0;

        int end = arrayA.length-1;

        while(start < end){

            char temp = arrayA[start];

            arrayA[start++] = arrayA[end];

            arrayA[end--] = temp;

        }

        return String.valueOf(arrayA);

    }

    //去掉字符串前面的0

    public String getNonoZeroString(String A){

        char[] arrayA = A.toCharArray();

        int count = 0;

        for(int i = 0;i < arrayA.length;i++){

            if(arrayA[i] == '0')

                count++;

            else

                break;

        }

        char[] result = new char[arrayA.length-count];

        for(int i = 0;i < arrayA.length-count;i++)

            result[i] = arrayA[count+i];

        return String.valueOf(result);

    }

    public static void main(String[] args){

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        //System.out.println("请输入一个正整数n:");

        int n = in.nextInt();

        in.nextLine();

        //System.out.println("请输入n个十六进制数：");

        String[] A = new String[n];

        for(int i = 0;i < n;i++){

            String temp = in.nextLine();

            A[i] = temp;

        }

        in.close();

        String[] result = new String[n];

        for(int i = 0;i < n;i++){

            result[i] = test.getTwoToEight(test.getSixteenToTwo(A[i]));

            System.out.println(result[i]);

        }

    }

}