from functools import wraps def memoize(function): memo = {} @wraps(function) def f(*args, **kwargs): key = args, tuple(sorted(kwargs.items())) if key not in memo: memo[key] = function(*args, **kwargs) return memo[key] f.memo = memo return f def check(n,a): ''' check if 'a' is good for this 'n' ''' if n > 2 and n % 4: assert a is None else: assert a is not None a = list(a) assert len(a) == n*n for i in xrange(n*n): assert a[i] in [-1,1] s = sum(a[(i%n)*n+(k%n)] * a[(i/n)*n+(k%n)] for k in xrange(n*n)) assert s == (n*n if (i%n) == (i/n) else 0) N = 100 isprime = [True]*(N+1) isprime[0] = isprime[1] = False isprimepow = [False]*(N+1) for p in xrange(2,N+1): for n in xrange(p<<1,N+1,p): isprime[n] = False if isprime[p]: n = p e = 1 while n <= N: isprimepow[n] = p, e n *= p e += 1 from itertools import * def all_monic_irreducibles(p): ''' yields all monic irreducibles modulo p ''' # sieve on the euclidean domain Z_p[x] def mul(a, b): # multiplication in Z_p[x] c = [0]*(len(a) + len(b) - 1) for i in xrange(len(a)): for j in xrange(len(b)): c[i+j] += a[i] * b[j] c[i+j] %= p return tuple(c) composites = set() all_pols = [] for d in count(1): new_pols = list(x + (1,) for x in product(xrange(p), repeat=d)) for P in new_pols: if P not in composites: composites.add(P) yield P all_pols.extend(new_pols) for P in new_pols: for Q in all_pols: composites.add(mul(P, Q)) from collections import defaultdict irrs = {} irrse = defaultdict(list) def find_irr(p, e): ''' find a monic irreducible polynomial modulo p with degree e ''' if p not in irrs: irrs[p] = all_monic_irreducibles(p) while (p,e) not in irrse: x = irrs[p].next() irrse[p,len(x)-1].append(x) return irrse[p,e][0] def replace(fa,fb): ''' tensor product ''' A = len(fa) B = len(fb) n = A * B grid = [[0]*n for i in xrange(n)] for i in xrange(n): for j in xrange(n): grid[i][j] = fa[i%A][j%A] * fb[i/A][j/A] return grid def shift(g,sign): n = len(g)+1 for i in xrange(len(g)): g[i].append(1) g.append([sign]*(n-1) + [0]) return g def addI(g): n = len(g) for i in xrange(n): g[i][i] += 1 return g x1 = [[1,1],[1,-1]] x0 = [[1,-1],[-1,-1]] def replace2(g): n = 2*len(g) grid = [[0]*n for i in xrange(n)] for i in xrange(n): for j in xrange(n): v = g[i/2][j/2] if v: grid[i][j] = v * x1[i%2][j%2] else: grid[i][j] = x0[i%2][j%2] return grid def williamson(A1,B1,C1,D1): ''' williamson construction ''' xs = map(list, [A1,B1,C1,D1]) k = len(xs[0]) n = 4*k grid = [[0]*n for i in xrange(n)] sign = [ [1,1,1,1], [-1,1,1,-1], [-1,-1,1,1], [-1,1,-1,1], ] for i in xrange(n): for j in xrange(n): grid[i][j] = sign[i/k][j/k] * xs[(i/k)^(j/k)][(j-i)%k] return grid def getq(n): ''' return a jacobsthal matrix of order n (a prime power) ''' p, e = isprimepow[n] pol = find_irr(p, e) assert len(pol) == e+1 assert pol[e] == 1 pols = list(product(xrange(p), repeat=e)) idx = {p:i for i, p in enumerate(pols)} def add(a, b): return tuple((x + y) % p for x, y in zip(a, b)) def sub(a, b): return tuple((x - y) % p for x, y in zip(a, b)) def mul(a, b): c = [0]*(2*e-1) for i in xrange(e): for j in xrange(e): c[i+j] += a[i] * b[j] c[i+j] %= p for i in xrange(2*e-2,e-1,-1): for j in xrange(1,e+1): c[i-j] -= c[i] * pol[e-j] c[i-j] %= p return tuple(c[:e]) def iadd(a, b): return idx[add(pols[a], pols[b])] def isub(a, b): return idx[sub(pols[a], pols[b])] def imul(a, b): return idx[mul(pols[a], pols[b])] chi = [-1]*n # quadratic character chi[0] = 0 for g in xrange(1,n): chi[imul(g, g)] = 1 return [[chi[isub(i,j)] for j in xrange(n)] for i in xrange(n)] @memoize def find(n): ''' find a hadamard matrix of order n ''' if n == 1: return [[1]] if n == 2: return [[1,1],[1,-1]] if n % 4: return None if n == 92: # special case A1 = [1, 1,-1,-1,-1, 1,-1,-1,-1, 1,-1, 1, 1,-1, 1,-1,-1,-1, 1,-1,-1,-1, 1] B1 = [1,-1, 1, 1,-1, 1, 1,-1,-1, 1, 1, 1, 1, 1, 1,-1,-1, 1, 1,-1, 1, 1,-1] C1 = [1, 1, 1,-1,-1,-1, 1, 1,-1, 1,-1, 1, 1,-1, 1,-1, 1, 1,-1,-1,-1, 1, 1] D1 = [1, 1, 1,-1, 1, 1, 1,-1, 1,-1,-1,-1,-1,-1,-1, 1,-1, 1, 1, 1,-1, 1, 1] return williamson(A1,B1,C1,D1) for a in xrange(2,n): if n % a == 0: b = n / a if find(a) and find(b): return replace(find(a),find(b)) if isprime[n-1]: return addI(shift(getq(n-1),-1)) if isprime[n/2-1] and (n/2-1) % 4 == 1: return replace2(shift(getq(n/2-1),1)) if isprimepow[n-1]: return addI(shift(getq(n-1),-1)) if isprimepow[n/2-1] and (n/2-1) % 4 == 1: return replace2(shift(getq(n/2-1),1)) @memoize def vfind(n): ''' find a good vector of order n ''' g = find(n) if g: assert len(g) == n assert all(len(row) == n for row in g) g = sum(g, []) return g for cas in xrange(input()): row = vfind(input()) if row: print 'YES' print ' '.join(map(str, row)) else: print 'NO'