Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"fmt"
	)

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	out := make([][]string, 100)
	for i := range out {
		out[i] = make([]string, 100)
	}
	dx := []int{0, 1, 0, -1}
	dy := []int{-1, 0, 1, 0}
	scanner.Scan()
	a, _ := strconv.Atoi(scanner.Text())
	for a > 0 {
		a--
		scanner.Scan()
		b, _ := strconv.Atoi(scanner.Text())
		for i := 0; i < b; i++ {
			for j := 0; j < b; j++ {
				out[i][j] = " "
			}
			out[i][b] = "0"
		}
		if b == 1 {
			fmt.Println("#")
			if a != 0 {
				fmt.Println()
			}
			continue
		}
		if b == 2 {
			fmt.Println("##")
			if a != 0 {
				fmt.Println()
				continue
			}
		}
		row := b -1
		col := 0
		dir := 0
		len := 0
		out[row][col] = "#"
		for {
			nrow := row+dy[dir%4]
			ncol := col+dx[dir%4]
			if dir%4 == 0 && nrow == 0 || dir%4==3&&ncol==0 || dir%4==2&&nrow==b-1 || dir%4==1&&ncol==b-1 {
				row=nrow
				col=ncol
				out[row][col]="#"
				dir++
				len = 1
			} else if out[nrow+dy[dir%4]][ncol+dx[dir%4]]=="#" {
				if len < 3 {
					break
				}
				dir++
				len = 1
			} else {
				row=nrow
				col=ncol
				out[row][col]="#"
				len++
			}
		}
		for i := 0; i < b; i++ {
			for j := 0; j < b; j++ {
				fmt.Printf("%s", out[i][j])
			}
			fmt.Println()
		}
		if a != 0 {
			fmt.Println()
		}
	}
}

C++: #include<iostream>
#include<cassert>
#include<ctime>
#include<climits>
#include<queue>
#include<fstream>
#include<deque>
#include<iomanip>
#include<list>
#include<stack>
#include<sstream>
#include<string>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define F first
#define S second
#define all(n) n.begin(),n.end()
#define pb push_back
#define insert(a,b,c,d) PP(P(a,b),P(c,d))
#define INF (1<<27)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<P,P> PP;
const int dx[4] = {-1,0,+1,0};
const int dy[4] = {0,-1,0,+1};

class Solve{
private:
  int d;
  int imap[110][110];
public:

  Solve(int n):d(n){}
  ~Solve(){}

  int Connect(P p){
    int cnt = 0;
    rep(i,4){
      int nx = p.F+dx[i],ny = p.S+dy[i];
      if(!(0<=nx && nx <d && 0<= ny && ny < d))continue;
      if(imap[ny][nx] == 1)cnt++;
    }
    return cnt;
  }


  void display(){
      cout << "--- in display ---" << endl;
      rep(i,d){
	rep(j,d){
	  if(imap[i][j] == 1)cout << '#';
	  else cout << ' ';
	}
	cout << endl;
      }
      cout << endl;
    }


  void run(){
    rep(i,d+1)rep(j,d+1)imap[i][j] = 0;

    rep(i,d){
      imap[0][i] = 1;
      imap[i][0] = 1;
      imap[i][d-1] = 1;
    }

  


    P pos = P(d-1,d-1);
    int dir = 0;
    int cnt = 0;
    bool fin = false;
    while(true){

      int nx,ny;
      nx  = pos.F,ny = pos.S;
      while(true){
	//cout << "nx = " << nx << ",ny = "<< ny << ",dir = " << dir << endl;
	//display();


	if(!(Connect(P(nx,ny)) == 2 || Connect(P(nx,ny)) == 1)){
	  imap[ny-dy[dir]][nx-dx[dir]] = 0;
	  //cout << "Lase nx = " << nx << ",ny = "<< ny << endl;
	  //cout << "FIN! connnect = " << Connect(P(nx,ny)) << endl;
	  fin = true;
	  break;
	}

	if(imap[ny+dy[dir]][nx+dx[dir]] == 1){
	  //cout << "IN nx = " << nx+dx[dir] << ",ny = " << ny+dy[dir] << endl;
	  imap[ny][nx] = 0;
	  cnt--;
	  break;
	}
	imap[ny][nx] = 1;
	cnt++;	


	nx += dx[dir],ny += dy[dir];
      }
      //cout << "------ cnt = " << cnt << endl;
      if(fin){
	//cout << "dir = " << dir << endl;
	break;
      }
      if(cnt == 0)break;
      cnt =0;

      pos.F = nx-dx[dir],pos.S = ny-dy[dir];
      dir++;
      dir = dir%4;
    }

    rep(i,d){
      rep(j,d){
	if(imap[i][j] == 1)cout << '#';
	else cout << ' ';
      }
      cout << endl;
    }
    

  }


};


int main(){
  int T;
  cin >> T;
  while(T-- > 0){
    int _n;
    cin >> _n;
    Solve ans = Solve(_n);
    ans.run();
    if(T != 0)cout << endl;
  }
return 0;
}

C++: #include <iostream>
using namespace std;
#define rep2(x,from,to) for(int x=(from);x<(to);++(x))
#define rep(x,to) rep2(x,0,to)
bool isOk(int i, int r, int c, bool b[104][104]) {
	if(i%2==0) {
		if(b[r][c-1]==0&&b[r][c+1]==0) {
			if(i==0?b[r-1][c]==0:b[r+1][c]==0) return true;
		}
	} else {
		if(b[r-1][c]==0&&b[r+1][c]==0) {
			if(i==1?b[r][c+1]==0:b[r][c-1]==0) return true;
		}
	}
	return false;
}
int main() {
	int n, a;
	cin >> n;
	bool f = 0;
	rep(i,n) {
		if(f) cout << endl;
		f = 1;
		cin >> a;
		bool b[100+4][100+4] = {};
		rep(i,a+4) {
			b[i][0] = 1;
			b[i][a+3] = 1;
			b[0][i] = 1;
			b[a+3][i] = 1;
		}
		int r = a+1, c = 2, cnt = 0;
		while(1) {
			if(!isOk(cnt, r, c, b)) break;
			while(isOk(cnt, r, c, b)) {
				b[r][c] = 1;
				switch(cnt) {
				case 0: r--;
					break;
				case 1: c++;
					break;
				case 2: r++;
					break;
				case 3: c--;
					break;
				}
			}
			cnt = (cnt+1) % 4;
			switch(cnt) {
				case 0: r--, c++;
					break;
				case 1: c++, r++;
					break;
				case 2: r++, c--;
					break;
				case 3: c--, r--;
					break;
			}
		}
		rep2(i,2,a+2) {
			rep2(j,2,a+2) {
				cout << (b[i][j] ? "#": " ");
			}
			cout << endl;
		}
	}
	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <complex>
#include <map>
#include <climits>
#include <sstream>
using namespace std;

#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second
#define mkp make_pair

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
static const int INF=1<<24;

template <class T>
void initvv(vector<vector<T> > &v,int a,int b, const T  &t = T()){
	v.assign(a,vector<T>(b,t));
}

//v.erase(unique(v.begin(),v.end()),v.end());

int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int main(){
	int n;
	cin>>n;
	rep(l,n){
		if(l) cout<<endl;
		int m;
		cin>>m;
		// cout<<m<<endl;
		if(m==1){
			cout<<"#\n";
			continue;
		}
		if(m==2){
			cout<<"##\n";
			cout<<"# \n";
			continue;
		}
		if(m==3){
			/*
			###
			# #
			# #
			*/
			cout<<"###\n";
			cout<<"# #\n";
			cout<<"# #\n";
			// cout<<"\n";
			continue;
		}
		if(m==4){
			cout<<"####\n";
			cout<<"#  #\n";
			cout<<"#  #\n";
			cout<<"# ##\n";
			// cout<<endl;
			continue;
		}
		vector<vector<char> > vv;
		initvv(vv,m,m);
		rep(i,m){
			rep(j,m) vv[i][j]=' ';
		}
		rep(i,m){
			vv[0][i]='#';
			vv[m-1][i]='#';
			vv[i][m-1]='#';
			vv[i][0]='#';
		}
		vv[m-1][1]=' ';
		int x=m-1,y=2;
		int c=0;
		while(1){
			// cout<<x<<" "<<y<<endl;
			if(vv[x+dx[c]*2][y+dy[c]*2]==' '){
				x+=dx[c];
				y+=dy[c];
				vv[x][y]='#';
			}
			else if(vv[x+2*dx[(c+1)%4]][y+2*dy[(c+1)%4]]==' '&&vv[x+dx[(c+1)%4+dx[(c+2)%4]]][y+dy[(c+1)%4]+dy[(c+2)%4]]==' '){
				c++;
				c%=4;
				x+=dx[c];
				y+=dy[c];
				vv[x][y]='#';
			}
			else{
				break;
			}
		}
		/*
		######
		#    #
		# ## #
		# #  #
		# #  #
		# ####
		*/
		rep(i,m){
			rep(j,m){
				cout<<vv[i][j];
			}
			cout<<endl;
		}
		cout<<endl;
	}
}