#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; bool safe(int i,int j,int n){ if((i>=0 && i=0 && j > v(n,vector(n,0)); queue> q; vector t(3,0); t[0]=0; t[1]=0; t[2]=0; q.push(t); int i,j,l; int maxl=0; while(!q.empty()){ vector e=q.front(); maxl = max(maxl,e[2]); i=e[0]; j=e[1]; l=e[2]+1; v[i][j]=1; q.pop(); if(i==n-1 && j==n-1) break; if(safe(i-a,j+b,n) && v[i-a][j+b]!=1){ v[i-a][j+b]=1; t[0]=i-a;t[1]=j+b;t[2]=l; q.push(t); } if(safe(i+b,j+a,n) && v[i+b][j+a]!=1){ v[i+b][j+a]=1; t[0]=i+b;t[1]=j+a;t[2]=l; q.push(t); } if(safe(i+a,j+b,n) && v[i+a][j+b]!=1){ v[i+a][j+b]=1; t[0]=i+a;t[1]=j+b;t[2]=l; q.push(t); } if(safe(i-a,j-b,n) && v[i-a][j-b]!=1){ v[i-a][j-b]=1; t[0]=i-a;t[1]=j-b;t[2]=l; q.push(t); } if(safe(i+a,j-b,n) && v[i+a][j-b]!=1){ v[i+a][j-b]=1; t[0]=i+a;t[1]=j-b;t[2]=l; q.push(t); } if(safe(i-b,j-a,n) && v[i-b][j-a]!=1){ v[i-b][j-a]=1; t[0]=i-b;t[1]=j-a;t[2]=l; q.push(t); } if(safe(i-b,j+a,n) && v[i-b][j+a]!=1){ v[i-b][j+a]=1; t[0]=i-b;t[1]=j+a;t[2]=l; q.push(t); } if(safe(i+b,j-a,n) && v[i+b][j-a]!=1){ v[i+b][j-a]=1; t[0]=i+b;t[1]=j-a;t[2]=l; q.push(t); } } if(i==n-1 && j==n-1) return maxl; else return -1; } int main(){ int n; cin >> n; for(int i=1;i