【问题描述】

　　给定n个十六进制正整数，输出它们对应的八进制数。

       输入格式

　　输入的第一行为一个正整数n （1<=n<=10）。

　　接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。输入的十六进制数不会有前导0，比如012A。

       输出格式

　　输出n行，每行为输入对应的八进制正整数。输出的八进制数也不能有前导0。

       样例输入

　　2

　　39

　　123ABC

       样例输出

　　71

　　4435274

       【编程思路1】

       我们知道，二进制数与八进制数或十六进制数之间存在直接转换关系。可以说，八或十六进制数是二进制数的缩写形式。在计算机中，利用这一特点可把用二进制代码表示的指令或数据写成八或十六进制形式，以便于书写或认读。 

      （1）二进制整数与八进制整数的转换。

        由于八进制的基数为8，二进制的基数为2，两者满足8=2³，故每位八进制数可转换为等值的三位二进制数，反之亦然。

        因此，八进制整数转换成二进制整数，只需把每位八进制数用相应的3位二进制数代替即可。而二进制整数转换成八进制整数，则将二进制整数从右到左分成三位一组，头部不足三位时补0，再将每组的三位二进制数写成一位八进制数，则得对应的八进制整数。

        （2）二进制数与十六进制数的转换。

        由于十六进制的基数为16，二进制的基数为2，两者满足16=2⁴，故每位十六进制数可转换为等值的四位二进制数，反之亦然。

        因此，十六进制整数转换成二进制整数，只需把每位十六进制数用相应的4位二进制数代替即可。而二进制整数转换成十六进制整数，则将二进制整数从右到左分成四位一组，头部不足四位时补0，然后将每组的四位二进制数写成一位十六进制数，则得对应的十六进制整数。 

        （3）八进制整数与十六进制整数的转换。

        可以用二进制数作为中间数制进行转换。即若要将十六进制整数转换为八进制整数，可以先将十六进制整数转换为相应的二进制整数，然后再将二进制整数转换为相应的八进制整数。

        以样例为例，若要转换的十六进制整数为39，转换为二进制整数时，每个数直接用4位二进制数来替换，写成00111001，去掉前导0，得到相应的二进制整数 为 111001。再将该二进制整数从右到左分成两组 111  001 ，每组分别用一个八进制数码来代替，写成 71，即对应的八进制整数为 71。

        若要转换的十六进制整数为 123ABC，转换为二进制整数时，每个数直接用4位二进制数来替换，写成 0001 0010 0011 1010 1011 1100，去掉前导0，得到相应的二进制整数 为 10010001110101011 1100。再将该二进制整数从右到左分成七组 100 100 011 101 010 111 100 ，每组分别用一个八进制数码来代替，写成 4 4 3 5 2 7 4，即对应的八进制整数为 4435274。

       按上面的方法，可以编写如下的源程序1。

        【源程序1】

#include <stdio.h>
#include <string.h>
int main()
{
    char  hex[100001],bin[400001];
    char table[16][5]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"};
    int n,i,num;
    scanf("%d",&n);
    while (n--)
    {
        scanf("%s",hex);
        if (hex[0]=='0')
        {
            printf("0\n");
            continue;
        }
        bin[0]='\0';
        for (i=0;hex[i]!='\0';i++)      // 将十六进制数中的每个数字用4位二进制数替换，从而将十六进制整数转换为对应的二进制整数 
        {
            num=hex[i]-'0';
            if (num>9) num=num-7;
            strcat(bin,table[num]);
        }
        for (i=0; bin[i]=='0';i++) ;   // 去掉二进制数的前导0
        strcpy(bin,&bin[i]);
        int len=strlen(bin);           // 将二进制整数从右到左每3位为一组
        if (len%3==0)                  // 先将头部的一组（若为1位或2位）转换为一个八进制数
           i=0;
        else if (len%3==1)
        {
           i=1;
           printf("1");
        }
        else
        {
           i=2;
           num=(bin[0]-'0')*2+(bin[1]-'0');
           printf("%d",num);
        }
        for (;i<len;i+=3)              // 再将后面的各组（每组均有3位），每组均转换为一个八进制数 
        {

           num=(bin[i]-'0')*4+(bin[i+1]-'0')*2+(bin[i+2]-'0');
           printf("%d",num);
        }
        printf("\n");
    }
    return 0;
}

        【编程思路2】

        上面的源程序1可以实现十六进制整数转换为八进制整数，但由于采用二进制数过渡时，产生的二进制数位数太多。这样，处理起来效率不高。在有些包含这个数制转换问题的OJ系统中，若提交类似源程序1所示的代码，会出现“运行超时”。因此，需要采用更高效的方法来处理。

       由前面源程序1可知，一个十六进制整数的1位可以用4位二进