import java.math.BigInteger;
import java.util.*;
public class Main{
  public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  int n = in.nextInt();
  for (int i = 0; i < n; ++i) {
    String s = in.next();
    BigInteger temp = new BigInteger(s, 16);
    System.out.println(temp.toString(8));
  }
  in.close();
  }
}

import java.util.*;
public class Main{
  public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  int n = in.nextInt();
  for (int i = 0; i < n; ++i) {
    String s = in.next();
    System.out.println(binToOct(henToBin(s)));
  }
  in.close();
  }
  // 十六进制转二进制
  public static StringBuilder henToBin(String s) {
  Map<Character, String> map = new HashMap<Character, String>();
  map.put('0', "0000");map.put('1', "0001");map.put('2', "0010");map.put('3', "0011");
  map.put('4', "0100");map.put('5', "0101");map.put('6', "0110");map.put('7', "0111");
  map.put('8', "1000");map.put('9', "1001");map.put('A', "1010");map.put('B', "1011");
  map.put('C', "1100");map.put('D', "1101");map.put('E', "1110");map.put('F', "1111");
  StringBuilder sb = new StringBuilder();
  final int len = s.length();
  for (int i = 0; i < len; ++i) {
    sb.append(map.get(s.charAt(i)));
  }
  return sb;
  }
  // 二进制转八进制
  public static StringBuilder binToOct(StringBuilder s) {
  Map<String, Character> map = new HashMap<String, Character>();
  map.put("000", '0');map.put("001", '1');map.put("010", '2');map.put("011", '3');
  map.put("100", '4');map.put("101", '5');map.put("110", '6');map.put("111", '7');
  StringBuilder sb = new StringBuilder();
  int len = s.length();
  // 长度变为3的倍数，便于转换
  int temp = len % 3;
  if (temp != 0) {
    s.insert(0, temp==1?"00":"0");
    len = s.length();
  }
  // 开始转换
  for (int i = 0; i < len; i+=3) {
    sb.append(map.get(s.substring(i, i+3)));
  }
  // 去除前面的0
  len = sb.length();
  for (int i = 0; i < len; ++i) {
    if (sb.charAt(i) == '0') {
    sb.deleteCharAt(i);
    } else {
    break;
    }
  }
  return sb;
  }
}