「题解」六边形

题目链接:GMOJ 2643

题目

题目描述

棋盘是由许多个六边形构成的,共有 $n$ 种不同的六边形编号为 $1$ 到 $5$,棋盘的生成规则如下:

  1. 从中心的一个六边形开始,逆时针向外生成一个个六边形。
  2. 对于刚生成的一个六边形,我们要确定它的种类,它的种类必须满足与已生成的相邻的六边形不同。
  3. 如果有多个种类可以选,我们选择出现次数最少的种类。
  4. 情况3下还有多个种类可以选,我们选择数字编号最小的。

现在要你求第 $N$ 个生成的六边形的编号。

前 $14$ 个六边形生成图如下:

【题解】六边形-Z1.png

输入格式

第一行:$T$,表示数据组数。
接下来 $T$ 行,每行一个数:$N$,表示第 $N$ 个六边形。

输出格式

共 $T$ 行,每行一个数,表示第 $N$ 个数据的答案。

样例输入输出

#1

  • Input:
4
1
4
10
100
  • Output
1
4
5
5

数据范围

$100\%$ 数据满足 $1\leq T\leq 20,1\leq N\leq 10^4$。
$30\%$ 数据满足 $1\leq N\leq 10^2$。

题解

本题有多种写法,下面介绍几种比较简单的。

解法A

思路

我们将整个大的图形分为多个部分,每个部分都是由 $6\times k,k\in\mathbb{N _ +}$(中心为特殊情况)个正六边形构成的一个圈。

我们考虑第 $i$ 圈,第 $j$ 个六边形的相邻六边形。

  1. 内圈的(1个或者2个)。
  2. 相邻的(前面和后面)。
  3. 外圈的(3个或者4个)。

于是我们考虑简化一下情况,决定递推,于是我们只需要考虑最多三个相邻六边形:

  1. 内圈的(1个或者2个)。
  2. 相邻的(前面)。

另外的,根据相似三角形的相关知识,我们可以求出:

内圈的序数为 $\left\lceil j\times\frac{i-2}{i-1}\right\rceil$ 和 $\left\lfloor j\times\frac{i-2}{i-1}\right\rfloor$。

另外,当一圈即将结束时,这个六边形将会碰到圈首的那个六边形,这需要特殊考虑,我们按照题意模拟即可。

代码

#include<cstdio>
#include<cstring>
#define INF 789846556
const int MAXN=20000+5;
bool Can[9];
int T,n;
int Number[MAXN]={0,1,6},sum[MAXN]={0,1,7};
int color[MAXN];
int Times[9];
void Init(void);
int GetID(int,int);
int GetLast(int,int);
int main(void){
    register int i,j;
    scanf("%d",&T);
    Init();
    while(T--){
        memset(color,0,sizeof(color));
        memset(Times,0,sizeof(Times));
        scanf("%d",&n);
        for(i=j=1;GetID(i-1,j-1)<=n;++i){
            for(j=1;j<=Number[i];++j){
                //printf("%d (%d,%d)\n",GetID(i,j),i,j);
                memset(Can,true,sizeof(Can));
                Can[color[GetID(i,j)-1]]=false;
                if(j*Number[i-1]%Number[i]==0){
                    if(j*Number[i-1]/Number[i]==0){
                        Can[color[GetID(i-1,Number[i-1])]]=false;
                        Can[color[GetID(i-1,1)]]=false;
                    }
                    else
                        Can[color[GetLast(i,j)]]=false;
                }
                else{
                    if(j*Number[i-1]/Number[i]==0){
                        Can[color[GetID(i-1,Number[i-1])]]=false;
                        Can[color[GetID(i-1,1)]]=false;
                    }
                    else{
                        Can[color[GetLast(i,j)]]=false;
                        Can[color[GetLast(i,j)+1]]=false;
                    }
                }
                if(j==Number[i])
                    Can[color[GetID(i,1)]]=false;
                int c=0,times=INF;
                for(int k=1;k<=5;++k)
                    if(Times[k]<times&&Can[k]){
                        c=k;
                        times=Times[k];
                    }
                color[GetID(i,j)]=c;
                ++Times[c];
            }
        }
        printf("%d\n",color[n]);
    }
    return 0;
}
void Init(void){
    register int i;
    for(i=3;sum[i-1]<20000;++i){
        Number[i]=Number[i-1]+6;
        sum[i]=sum[i-1]+Number[i];
        //printf("Number[%d]=%d sum[%d]=%d\n",i,Number[i],i,sum[i]);
    }
    return;
}
int GetID(int i,int j){
    return sum[i-1]+j;
}
int GetLast(int i,int j){
    return GetID(i-1,j*Number[i-1]/Number[i]);
}

解法B

显然,每个六边形的周围都有六个与它相邻的六边形(因为它有六条边)。
那么我们开数组 $\text{Next} _ {i,x}$ 表示与第 $i$ 个六边形相邻的第 $x$ 个六边形的编号。
考虑初始化的情况后枚举即可。

代码略。

解法C

这是一种新奇的构造法。

我们将六边形压缩进入一个矩阵。

解法可见传送门

解法D

这是四种写法中最快速的一种,但它的前置技能是上述任意一种解法。
这种解法无需详细的思路,十分显然,一看就懂,直接上代码。

#include<cstdio>
const int ans[]={0,1,2,3,4,5,2,3,1,4,5,1,2,3,1,4,3,5,4,2,5,2,1,3,4,5,3,1,2,4,5,1,2,4,3,1,5,3,2,4,5,2,4,1,3,1,2,5,3,4,5,1,2,3,4,5,1,2,4,3,1,5,3,5,2,4,1,3,2,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,2,1,5,4,3,5,2,3,4,1,5,1,3,4,5,2,3,1,2,4,5,1,2,3,4,5,3,1,2,1,4,5,2,4,3,5,3,2,1,2,5,4,1,4,5,1,3,2,3,4,5,1,2,3,4,5,3,1,2,1,4,5,4,2,3,1,2,5,3,4,5,1,2,3,5,1,4,2,4,3,5,3,1,2,5,2,1,4,3,4,5,1,2,3,4,5,3,1,2,1,4,5,3,4,5,2,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,5,1,2,4,3,4,5,3,1,4,5,2,1,2,5,3,4,3,1,2,1,4,2,5,3,4,5,1,2,5,3,1,4,3,4,5,2,1,3,4,5,2,3,1,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,5,3,4,2,3,1,4,5,2,3,1,4,5,1,2,3,4,5,1,3,4,2,5,1,2,3,4,1,5,2,3,5,1,2,4,3,4,5,1,2,3,4,5,3,1,2,4,5,1,4,2,3,2,5,1,5,3,4,3,1,4,2,5,1,4,2,3,1,3,5,4,2,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,3,1,2,1,4,5,3,5,2,4,2,3,1,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,5,4,2,4,1,3,1,5,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,5,4,1,4,2,3,2,5,1,5,3,4,1,2,3,4,5,1,2,4,3,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,5,2,4,1,4,3,1,5,3,2,4,5,1,2,3,4,5,3,1,2,1,4,5,4,3,2,3,5,1,2,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,4,5,1,3,4,2,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,5,2,4,3,1,4,2,1,5,3,1,4,5,4,2,3,1,2,5,3,4,5,1,2,5,4,1,2,3,4,3,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,2,4,3,4,5,1,4,2,3,5,1,2,3,4,5,1,2,5,3,4,3,1,2,1,5,4,5,2,3,1,2,5,4,3,1,4,2,4,5,3,1,2,3,4,5,2,3,1,4,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,5,3,4,2,1,4,1,3,5,4,2,3,2,5,1,3,4,5,1,2,3,4,2,1,3,4,5,2,5,1,3,1,5,4,2,3,5,1,4,2,3,4,5,1,3,4,5,2,3,1,2,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,2,3,1,4,5,1,3,2,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,5,1,4,3,2,4,5,2,3,1,5,4,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,3,1,2,4,5,1,2,3,4,5,1,3,2,1,4,5,4,2,3,1,5,2,5,3,4,3,1,2,1,4,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,4,2,5,1,2,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,2,3,1,5,4,1,2,3,5,4,1,2,3,4,5,3,1,2,1,4,5,3,5,2,4,3,1,2,1,4,5,4,3,5,2,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,4,5,1,3,4,2,3,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,4,2,3,1,5,2,3,1,5,4,5,2,3,2,4,1,5,3,4,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,5,4,1,3,4,3,5,2,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,4,2,3,5,1,2,4,3,5,1,2,3,4,5,1,2,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,4,3,5,2,3,1,4,5,2,1,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,1,5,2,4,5,1,2,3,4,5,1,3,4,2,3,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,4,2,3,2,5,1,4,1,3,5,3,2,4,2,5,1,5,3,4,3,1,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,3,4,2,5,1,3,4,2,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,4,2,3,5,1,2,3,4,5,3,1,2,1,4,5,4,3,2,3,5,1,2,1,4,5,4,2,3,2,5,3,1,4,5,1,2,3,5,4,1,2,4,3,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,1,2,5,4,5,1,3,4,2,5,1,3,4,3,1,2,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,4,2,3,2,5,1,5,3,4,2,1,4,1,3,5,4,2,3,1,2,5,3,4,5,1,2,5,4,1,2,3,4,3,5,1,2,3,4,5,1,2,4,5,3,1,2,3,4,1,2,5,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,2,3,4,5,1,5,3,2,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,3,1,2,1,4,5,4,2,3,2,5,1,4,3,5,3,1,2,1,4,5,4,2,1,3,5,2,3,4,5,1,2,3,4,5,1,3,2,5,4,1,2,3,4,5,2,3,1,4,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,1,2,3,5,1,4,5,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,2,1,5,3,1,4,5,4,2,3,2,1,5,1,3,4,5,4,2,3,1,2,5,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,4,5,3,1,2,3,4,5,1,3,4,5,2,3,1,2,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,1,4,5,2,3,4,5,1,2,5,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,4,5,4,2,3,2,5,3,1,5,1,4,2,4,5,3,1,2,3,4,5,3,2,4,5,1,2,1,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,3,1,2,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,4,2,3,2,5,1,5,4,3,4,1,2,3,2,5,1,4,3,1,3,5,2,1,4,5,3,4,2,5,1,2,3,4,2,1,3,4,5,1,5,2,3,4,5,1,2,3,4,5,1,2,4,5,3,2,3,1,5,1,4,2,3,4,5,1,2,4,3,1,2,5,3,4,5,1,3,4,5,2,3,1,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,3,1,2,1,4,5,3,5,2,4,3,1,2,1,4,5,4,3,2,3,5,1,2,1,4,5,2,3,4,5,1,2,3,1,5,2,3,4,5,4,1,2,3,5,4,2,1,3,4,5,1,2,4,5,3,1,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,5,2,3,4,3,1,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,3,1,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,3,2,4,2,5,1,5,3,4,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,5,4,1,2,3,4,3,5,1,2,3,4,5,1,2,3,4,5,2,1,4,5,3,1,2,3,4,1,2,5,3,4,5,1,2,3,5,1,2,4,5,3,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,3,1,2,1,4,5,3,5,2,4,3,1,2,1,4,5,4,2,3,2,1,5,1,3,4,5,4,2,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,5,3,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,1,4,2,3,1,2,5,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,3,2,4,5,1,2,1,3,4,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,1,5,2,3,4,5,1,2,5,3,4,3,1,2,5,2,4,1,5,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,4,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,2,3,1,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,4,3,1,2,5,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,3,2,4,2,5,1,5,3,4,1,4,2,3,2,5,1,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,2,1,3,4,5,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,4,2,5,1,3,4,5,2,3,1,2,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,3,1,2,1,4,5,4,2,3,2,5,1,4,3,5,3,1,2,1,4,5,4,2,3,2,5,1,3,1,4,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,3,1,2,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,1,4,5,4,2,3,2,1,5,1,3,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,5,4,5,2,3,4,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,3,1,2,1,4,5,3,5,2,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,4,5,4,2,3,2,1,5,4,5,3,1,2,3,4,5,3,2,4,5,1,2,1,3,4,5,1,2,3,4,5,1,2,3,4,2,1,3,4,5,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,3,2,1,2,5,3,4,5,1,2,4,3,5,1,2,3,4,2,1,3,4,5,1,5,2,3,4,5,1,2,3,4,5,3,2,1,5,1,4,2,3,4,5,1,2,4,3,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,3,2,4,5,1,2,5,3,4,3,1,2,1,4,5,4,2,3,1,5,2,5,3,4,3,1,2,1,4,5,4,2,3,5,3,1,2,1,4,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,5,4,3,2,3,1,4,5,1,2,3,5,1,4,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,2,3,4,5,1,2,4,3,2,1,3,5,1,4,5,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,4,3,5,3,1,2,1,4,5,4,3,2,3,5,1,4,2,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,4,3,5,2,3,1,2,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,4,3,2,5,1,2,3,1,4,5,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,5,4,1,4,2,3,2,5,1,5,3,4,3,1,2,1,5,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,5,4,1,2,3,4,3,5,1,2,3,4,5,1,2,3,4,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,1,5,4,2,3,4,5,3,1,2,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,4,3,1,2,5,4,2,3,1,3,5,2,1,4,5,4,2,3,2,1,5,1,3,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,5,2,4,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,2,1,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,1,5,3,4,2,1,4,5,3,5,2,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,4,5,2,4,5,3,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,3,2,4,5,1,2,1,3,4,5,1,2,3,4,5,1,2,3,4,2,1,3,5,1,5,2,4,3,4,5,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,4,3,1,2,5,3,4,5,1,2,4,3,5,1,2,3,4,2,1,3,4,5,1,5,2,3,4,2,1,3,4,5,1,5,2,3,4,5,1,3,5,2,1,4,2,3,4,5,1,3,4,2,5,1,2,3,4,5,1,2,4,3,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,1,2,3,4,5,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,3,5,2,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,2,1,3,1,4,5,4,2,3,2,5,1,5,3,4,3,2,1,2,4,5,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,2,3,1,4,5,1,2,3,5,1,4,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,2,4,1,3,5,3,2,5,4,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,4,2,3,2,1,5,1,3,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,1,5,1,3,4,5,4,2,3,2,5,1,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,4,3,5,1,2,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,2,1,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,2,4,1,3,1,5,3,2,5,4,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,1,4,5,4,2,3,2,1,5,1,3,4,5,4,2,3,2,5,1,5,3,4,3,2,1,2,4,5,1,5,3,4,3,1,2,1,4,5,2,3,4,5,3,2,4,5,1,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,3,2,4,5,1,2,1,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,2,1,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,2,4,1,5,3,1,4,3,2,5,3,1,2,1,4,5,4,3,2,3,5,1,2,1,4,5,4,2,3,2,1,5,1,3,4,5,4,2,3,2,5,1,5,3,4,1,3,2,4,5,1,2,3,4,5,3,2,4,5,1,2,1,3,4,5,1,2,3,4,5,1,4,3,5,1,2,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,1,2,5,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,3,5,2,1,4,5,2,5,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,5,4,5,2,3,4,1,2,3,4,1,5,2,5,4,3,1,2,3,4,5,1,2,5,4,1,2,3,4,3,5,1,2,3,4,5,3,2,4,5,1,2,1,3,4,5,1,2,3,4,5,1,2,4,5,3,1,2,3,4,5,1,2,4,3,1,2,5,3,4,5,1,2,3,4,5,1,2,3,5,4,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,4,1,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,5,4,2,1,3,4,5,1,3,4,2,5,1,2,3,4,2,1,3,4,5,1,5,2,3,4,2,1,3,4,5,1,5,2,3,4,2,1,3,4,5,1,5,3,4,2,5,2,3,1,4,1,5,2,3,4,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,1,2,4,3,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,5,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,4,3,4,1,2,3,2,5,1,5,3,4,3,1,2,1,4,5,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,3,4,2,5,1,2,4,5,3,1,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,3,2,5,1,4,2,4,5,3,1,3,4,5,2,3,2,4,1,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,4,2,3,2,5,1,5,3,4,3,1,2,5,4,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,1,4,2,3,2,5,1,3,4,5,1,2,3,4,2,1,3,4,5,1,5,2,3,4,5,1,2,3,4,5,1,2,3,1,5,2,3,4,5,4,1,2,3,4,5,1,2,3,4,5,1,2,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,3,2,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,1,2,4,5,3,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,3,1,2,1,4,5,3,2,4,2,5,1,5,3,4,3,1,2,5,4,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,2,5,3,4,3,1,2,1,4,5,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,3,2,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,4,5,3,4,1,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,3,1,4,5,4,2,3,2,5,1,5,3,4,1,4,2,3,2,5,1,5,3,4,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,1,4,5,4,3,2,3,5,1,2,4,2,5,1,5,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,4,5,3,2,1,4,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,5,3,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,4,2,3,2,5,1,5,4,3,4,1,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,2,3,1,4,5,1,2,5,4,1,2,3,4,3,5,1,2,3,4,5,1,2,3,4,2,1,3,4,5,1,5,2,3,4,2,1,3,4,5,1,5,2,3,4,5,1,2,4,3,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,4,3,5,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,4,2,5,1,5,3,4,3,1,2,1,4,5,2,3,4,5,1,2,3,1,5,2,3,4,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,4,2,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,1,5,2,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,3,2,3,5,1,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,3,1,2,1,4,5,4,2,3,2,5,1,4,3,5,3,1,2,1,4,5,4,2,3,1,5,2,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,4,3,4,1,2,3,2,5,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,5,4,1,2,3,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,4,5,4,3,2,3,5,1,2,1,4,2,5,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2
    ,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,1,5,2,3,4,5,4,1,2,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,3,1,2,1,4,5,4,3,2,3,5,1,2,1,4,5,4,3,2,3,5,1,2,1,4,5,4,2,3,2,5,1,4,3,5,3,1,2,1,4,5,4,2,3,5,3,1,2,1,4,5,4,2,5,3,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,2,1,3,4,5,1,5,2,3,4,5,1,2,5,4,1,2,3,4,3,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,1,2,3,4,5,1,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,4,5,3,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,3,2,4,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,1,2,3,4,5,1,2,5,4,1,2,3,4,3,5,1,2,5,4,1,2,3,4,3,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,1,2,3,4,1,2,5,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,5,1,4,2,3,4,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,5,2,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,5,4,1,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,1,5,1,3,4,5,4,2,3,2,5,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,1,2,3,4,1,2,5,3,4,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,1,2,4,5,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,4,2,3,2,5,1,5,4,3,4,1,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,3,2,3,5,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,3,2,4,5,1,2,1,3,4,5,1,2,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,3,1,2,1,4,5,4,3,2,3,5,1,2,1,4,5,4,2,3,2,1,5,1,3,4,5,4,2,3,2,5,1,3,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,4,5,3,2,4,2,5,3,1,4,5,1,2,3,1,5,2,3,4,5,4,1,2,3,4,5,1,2,3,4,5,1,2,5,4,1,2,3,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,1,4,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,3,1,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,1,2,5,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,3,2,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,1,4,5,4,2,3,2,5,1,5,4,3,4,1,2,3,2,5,1,5,3,4,3,1,2,1,4,5,4,2,3,2,5,1,5,3,4,3,1,2,1,5,4,5,2,3,4,3,1,2,1,4,5,4,3,2,1,2,5,3,4,5,1,2,5,4,1,2,3,4,3,5,1,2,3,4,5,3,2,4,5,1,2,1,3,4,5,1,2,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,4,5,3,1,2,3,4,5,2,1,4,5,3,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,3,4,2,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,2,1,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,5,2,3,4,5,1,2,3,4,5,1,2,4,3,5,1,2,3,4,5,1,2,3,4,5,1,2,3,5,4};
int T,n;
int main(void){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%d\n",ans[n]);
    }
    return 0;
}