{$APPTYPE CONSOLE}
{$I-,S-,Q-,R-,O+}

uses
  TestLib, SysUtils;

const
  MaxL = 130;
  Deg = 100000000;
  LgDeg = 8;

type
  TLong = Array[1..MaxL] of LongInt;

var
  TCnt, TNum: LongInt;
  S: AnsiString;
  Find: Boolean;
  n: LongInt;
  i: LongInt;

Function IsSquare(S: AnsiString): Boolean;
var
  X: AnsiString;
  _X: TLong;
  L, R, C: TLong;
  L2, LR, R2: TLong;
  One: TLong;
  C2: TLong;
  Tmp: LongInt;
  i: LongInt;

Procedure Find_X;
var
  pos: LongInt;
  S: AnsiString;

begin
  pos:= 1;
  While X<>'' do begin
    If Length(X) > LgDeg
      then begin
        S:= Copy(X, Length(X)-LgDeg+1, LgDeg);
        Delete(X, Length(X)-LgDeg+1, LgDeg);
        _X[pos]:= StrToInt(S);
      end
      else begin
        _X[pos]:= StrToInt(X);
        X:= '';
      end;
    Inc(pos);
  end;
end;

Procedure Sum(A, B: TLong; var C: TLong);
var
  i: LongInt;

begin
  For i:= 1 to MaxL do
    C[i]:= A[i]+B[i];
  For i:= 1 to MaxL-1 do
  While C[i] >= Deg do begin
    Dec(C[i], Deg);
    Inc(C[i+1]);
  end;
end;

Procedure DivL(A: TLong; B: LongInt; var C: TLong);
var
  X: LongInt;
  i: LongInt;
  Bt: LongInt;

begin
  If B = 4
    then Bt:= 2
    else Bt:= 1;
  X:= 0;
  For i:= MaxL downto 1 do begin
    X:= Deg * X + A[i];
    C[i]:= X shr Bt;
    X:= X - C[i] * B;
  end;
end;

Function Eq(A, B: TLong): Boolean;
var
  i: LongInt;

begin
  Eq:= True;
  For i:= 1 to MaxL do
  If A[i] <> B[i] then begin
    Eq:= False;
    Exit;
  end;
end;

Procedure Sub(A, B: TLong; var C: TLong);
var
  i: LongInt;

begin
  For i:= 1 to MaxL do
    C[i]:= A[i]-B[i];
  For i:= 1 to MaxL-1 do
  While C[i] < 0 do begin
    Inc(C[i], Deg);
    Dec(C[i+1]);
  end;
end;

Function CmpL(A, B: TLong): LongInt;
var
  i: LongInt;

begin
  i:= MaxL;
  While (A[i] = B[i]) and (i>1) do
    dec(i);
  If A[i]>B[i]
    then CmpL:= 1
    else
      If A[i] < B[i]
        then CmpL:= -1
        else CmpL:= 0;
end;

begin
  X:= S;
  If X = '1' then begin
    WriteLn(1);
    Exit;
  end;
  FillChar(L, SizeOf(L), 0);
  L[1]:= 0;
  One:= L;
  One[1]:= 1;
  FillChar(_X, SizeOf(_X), 0);
  Find_X;
  L2:= L;
  i:= 1;
  While True do begin
    FillChar(R, SizeOf(R), 0);
    FillChar(R2, SizeOf(R2), 0);
    R[i]:= 1;
    R2[2*i-1]:= 1;
    If CmpL(R2, _X) > 0
      then Break;
    Inc(i);
  end;
  LR:= L;
  While True do begin
    Sum(L, R, C);
    Tmp:= C[1];
    DivL(C, 2, C);
    If (CmpL(L, C) = 0) or (CmpL(R, C) = 0)
      then Break;
    If Tmp mod 2 = 0 then begin
      C2:= L2;
      For i:= 1 to MaxL do
        C2[i]:= C2[i] + R2[i] + LR[i];
      Sum(C2, LR, C2);
      DivL(C2, 4, C2);
    end else begin
      C2:= L2;
      For i:= 1 to MaxL do
        C2[i]:= C2[i] + R2[i] + LR[i] + LR[i];
      Sum(C2, One, C2);
      Sub(C2, L, C2);
      Sub(C2, L, C2);
      Sub(C2, R, C2);
      Sub(C2, R, C2);
      DivL(C2, 4, C2);
    end;
    If (CmpL(C2, _X) <= 0) then begin
      L:= C;
      L2:= C2;
      If Tmp mod 2 = 0 then begin
        Sum(LR, R2, LR);
        DivL(LR, 2, LR);
      end else begin
        Sum(LR, R2, LR);
        Sub(LR, R, LR);
        DivL(LR, 2, LR);
      end;
    end else begin
      R:= C;
      R2:= C2;
      If Tmp mod 2 = 0 then begin
        Sum(LR, L2, LR);
        DivL(LR, 2, LR);
      end else begin
        Sum(LR, L2, LR);
        Sub(LR, L, LR);
        DivL(LR, 2, LR);
      end;
    end;
  end;
  IsSquare:= CmpL(L2, _X) = 0; 
end;

begin
  TCnt:= ouf.ReadLongInt;
  For TNum:= 1 to TCnt do begin
    n:= ouf.ReadLongInt;
    S:= ans.ReadWord(Blanks, Blanks);
    For i:= 1 to Length(S) do
      If not (S[i] in ['0'..'9'])
        then Quit(_PE, 'Bad character in output file: ' + S[i]);
    If Length(S) <> 2 * n
      then Quit(_WA, 'Incorrect number of digits in output for testcase ' + IntToStr(TNum) +
                     ': excepted ' + IntToStr(2 * n) + ', but got ' + IntToStr(Length(S)));
    If S[1] = '0'
      then Quit(_WA, 'Output for testcase ' + IntToStr(TNum) + ' has leading zero');
    Find:= False;
    For i:= n+1 to 2*n do
      If S[i] <> '0' then begin
        Find:= True;
        Break;
      end;
    If not Find
      then Quit(_WA, 'Second part of output for testcase ' + IntToStr(TNum) + ' contains only zeroes');
    If not IsSquare(Copy(S, 1, 2*n))
      then Quit(_WA, 'Output for testcase ' + IntToStr(TNum) + ' is not perfect square');
    If not IsSquare(Copy(S, 1, n))
      then Quit(_WA, 'First part of output for testcase ' + IntToStr(TNum) + ' is not perfect square');
    If not IsSquare(Copy(S, n+1, 2*n))
      then Quit(_WA, 'Second part of output for testcase ' + IntToStr(TNum) + ' is not perfect square');
  end;
  Quit(_OK, 'Ok!');
end.