CodeEff/ECCO huggingface dataset:
# Original solution
h, w, n = list(map(int, input().split()))
xy = sorted([list(map(int, input().split())) for _ in range(n)])
dx = 0
dy = 0
for x, y in xy:
  x -= dx
  y -= dy
  if x == y:
    dx += x-1
    dy += y-2
  elif y < x:
    print((dx+x-1))
    break
else:
  print(h)

# Optimized solution
import sys
input = sys.stdin.readline

def main():
  h, w, n = list(map(int, input().split()))
  xy = sorted([list(map(int, input().split())) for _ in range(n)])
  dx = 0
  dy = 0
  for x, y in xy:
    x -= dx
    y -= dy
    if x == y:
      dx += x-1
      dy += y-2
    elif y < x:
      print((dx+x-1))
      break
  else:
    print(h)
    
if __name__ == "__main__":
  main()
# Original solution
x,y,num = list(map(int, input().split()))
gaiz = []
zen_gaiz = [[] for _ in range(x)]
kaisu = x
for _ in range(num):
    xg,yg = list(map(int,input().split()))
    if xg >= yg:
        zen_gaiz[xg-1].append(yg)
        if xg != yg:
            gaiz.append((xg,yg))

if len(gaiz) ==0:
    print(kaisu)
else:
    finish = False
    for gai in sorted(gaiz, key=lambda x: x[0]):
        hidari = [gai[0]-1, gai[1]]
        while True:
            if hidari[1]==1: 
                kaisu = gai[0]-1
                finish=True
                break
            for g in zen_gaiz:
                if hidari[1] in zen_gaiz[hidari[0]-1]:
                    break
            else:
                hidari[0]-=1
                hidari[1]-=1
                continue
            break
        if finish:
            break
    print(kaisu) 
                

# Optimized solution
x,y,num = list(map(int, input().split()))
gaiz = [x]*x
kaisu = x
for _ in range(num):
    xg,yg = list(map(int,input().split()))
    if xg >= yg:
        sa = xg-yg
        if yg < gaiz[sa]:
            gaiz[sa]=(yg)
 
if len(gaiz) ==0:
    print(kaisu)
else:
    for num,(maegai,gai) in enumerate(zip(gaiz[:-1],gaiz[1:])):
        if maegai>gai and num+gai < kaisu:
            kaisu = num+gai
    print(kaisu)
# Original solution
# 解説 AC

# 参考1: https://twitter.com/rickytheta/status/1175412019006074880
# 参考2: https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-09-21agc-038

mod = 998244353
max_A = 10**6
N = int(eval(input()))
A = list(map(int, input().split()))

is_prime = [False, True, False, False, False, True] * (max_A//6+1)
del is_prime[max_A+1:]
is_prime[1:4] = False, True, True
for i in range(5, int(max_A**0.5)+1):
    if is_prime[i]:
        is_prime[i*i::i] = [False] * (max_A//i-i+1)
primes = [p for p, is_p in enumerate(is_prime) if is_p]  # max_A 以下の素数のリスト

g = [0] * (max_A+1)
for a in A:
    g[a] += a
for p in primes:
    # 倍数集合の高速ゼータ変換みたいなやつ  O((max_A)loglog(max_A))
    # 参考: http://noshi91.hatenablog.com/entry/2018/12/27/121649
    # 大量に約数列挙みたいなことをするときはこれで高速化できる場合が多そう？（みんぷろ 2018 本戦 A - Uncommon など）
    for k in range(max_A//p, 0, -1):
        g[k] += g[k*p]
g = [v * v % mod for v in g]
for p in primes:
    for k, g_kp in enumerate(g[p::p], 1):
        g[k] -= g_kp

modinv = [0, 1]
for i in range(2, max_A+1):
    modinv.append(mod - mod//i * modinv[mod%i] % mod)
ans = sum((gg * minv % mod for gg, minv in zip(g, modinv)))
ans %= mod
ans -= sum(A)
ans *= modinv[2]
ans %= mod
print(ans)


# Optimized solution
def main():
    mod = 998244353
    max_A = 10**6
    N = int(eval(input()))
    A = list(map(int, input().split()))

    is_prime = [False, True, False, False, False, True] * (max_A//6+1)
    del is_prime[max_A+1:]
    is_prime[1:4] = False, True, True
    for i in range(5, int(max_A**0.5)+1):
        if is_prime[i]:
            is_prime[i*i::i] = [False] * (max_A//i-i+1)
    primes = [p for p, is_p in enumerate(is_prime) if is_p]  # max_A 以下の素数のリスト

    g = [0] * (max_A+1)
    for a in A:
        g[a] += a
    for p in primes:
        # 倍数集合の高速ゼータ変換みたいなやつ  O((max_A)loglog(max_A))
        # 参考: http://noshi91.hatenablog.com/entry/2018/12/27/121649
        # 大量に約数列挙みたいなことをするときはこれで高速化できる場合が多そう？（みんぷろ 2018 本戦 A - Uncommon など）
        for k in range(max_A//p, 0, -1):
            g[k] += g[k*p]
    g = [v * v % mod for v in g]
    for p in primes:
        for k, g_kp in enumerate(g[p::p], 1):
            g[k] -= g_kp

    modinv = [0, 1]
    for i in range(2, max_A+1):
        modinv.append(mod - mod//i * modinv[mod%i] % mod)
    ans = sum((gg * minv % mod for gg, minv in zip(g, modinv)))
    ans %= mod
    ans -= sum(A)
    ans *= modinv[2]
    ans %= mod
    print(ans)
main()
# Original solution
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: list(map(int, readline().split()))
nl = lambda: list(map(int, readline().split()))

def make_modinv_list(n, mod=10**9+7):
    inv_list = [0]*(n+1)
    inv_list[1] = 1
    for i in range(2, n+1):
        inv_list[i] = (mod - mod//i * inv_list[mod%i] % mod)
    return inv_list

def solve():
  mod = 998244353
  n = ni()
  a = nl()
  m = max(a)
  s = -sum(a) % mod
  l = [0]*(m+1)
  for x in a:
    l[x] += x
  a = make_modinv_list(m, mod)
  sieve = [1]*(m+1)
  sieve[0] = sieve[1] = 0
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(m//i, 0, -1):
        sieve[j*i] = 0
        l[j] += l[j*i]
      sieve[i] = 1
  for i in range(m+1):
    l[i] = l[i] * l[i] % mod
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(1, m//i + 1):
        l[j] = (l[j] - l[j*i]) % mod
  for i in range(1, m+1):
    if l[i]:
      s = (s + l[i] * a[i]) % mod
  print((s * a[2] % mod))
  return

solve()

# Optimized solution
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: list(map(int, readline().split()))
nl = lambda: list(map(int, readline().split()))

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int((n+1)**0.5)+1):
        if is_prime[i]:
            for j in range(i *2, n + 1, i):
                is_prime[j] = False
    res = [i for i in range(n+1) if is_prime[i]]
    return res

def make_modinv_list(n, mod=10**9+7):
    inv_list = [0]*(n+1)
    inv_list[1] = 1
    for i in range(2, n+1):
        inv_list[i] = (mod - mod//i * inv_list[mod%i] % mod)
    return inv_list

def solve():
  mod = 998244353
  n = ni()
  a = nl()
  m = max(a)
  s = -sum(a) % mod
  l = [0]*(m+1)
  for x in a:
    l[x] += x
  a = make_modinv_list(m, mod)
  pr = primes(m) 
  for i in pr:
    for j in range(m//i, 0, -1):
      l[j] += l[j*i]
  for i in range(m+1):
    l[i] = l[i] * l[i] % mod
  for i in pr:
    for j in range(1, m//i + 1):
      l[j] = (l[j] - l[j*i]) % mod
  for i in range(1, m+1):
    if l[i]:
      s = (s + l[i] * a[i]) % mod
  print((s * a[2] % mod))
  return

solve()
# Original solution
import sys
sys.setrecursionlimit(4100000)

n=int(eval(input()))
A=[int(x) for x in input().split()]
import itertools
#import fractions
from functools import lru_cache
#com = list(itertools.combinations(A, 2))
res = 0
waru=998244353

@lru_cache(maxsize=None)
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a % b)

@lru_cache(maxsize=None)
def lcm(x,y):
    r = (x * y) // gcd(x, y) % waru
    return r

@lru_cache(maxsize=None)
def goukei(i,j):
    if j < n-1:
        return lcm(A[i],A[j]) + goukei(i,j+1)
    else:
        return lcm(A[i],A[j])

for i in range(n-1):
    res += goukei(i,i+1)
#for a, b in com:
    #res += lcm(a,b)

print((res % waru))



# Optimized solution
import sys
sys.setrecursionlimit(4100000)

n=int(eval(input()))
A=[int(x) for x in input().split()]
import itertools
#import fractions
from functools import lru_cache
#com = list(itertools.combinations(A, 2))
res = 0
waru=998244353

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a % b)

@lru_cache(maxsize=None)
def lcm(x,y):
    r = (x * y) // gcd(x, y) % waru
    return r

@lru_cache(maxsize=None)
def goukei(i,j):
    if j < n-1:
        return lcm(A[i],A[j]) + goukei(i,j+1)
    else:
        return lcm(A[i],A[j])

i=n-2
while i >= 0:
    res += goukei(i,i+1)
    i-=1
#for i in range(n-1):
    #res += goukei(i,i+1)
#for a, b in com:
    #res += lcm(a,b)

print((res % waru))
# Original solution
# coding: utf-8
# Your code here!
SIZE=1000003; MOD=998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
inv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(eval(input()))
a = [int(i) for i in readline().split()]

num = [0]*SIZE
db = [0]*SIZE
for i in a:
    num[i] += i
    db[i] += i*i
    db[i] %= MOD

def zeta(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(n//p,0,-1):
                sieve[k*p] = False
                a[k] += a[k*p]
                a[k] %= MOD
    return a


def meb(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(1,n):
                if k*p >= n: break
                sieve[k*p] = False
                a[k] -= a[k*p] 
                a[k] %= MOD
    return a


#n = 1000000

n = 1000001

#zn = [i*i for i in zeta(num,n)]
#zdb = zeta(db,n)
#print(zn[:20])
#print(zdb[:20])

zn = [i*i for i in zeta(num,n)]
zdb = zeta(db,n)
ans = [i-j for i,j in zip(zn, zdb)]

#ans = [i*i-j for i,j in zip(zeta(num,n), zeta(db,n))]

#print(ans[:20])
#print(meb(ans,n)[:20])

res = 0
for i,c in enumerate(meb(ans,n)):
    res = (res + c*inv[i])%MOD
        
print((res*inv[2]%MOD))









# Optimized solution
# coding: utf-8
# Your code here!
SIZE=1000001; MOD=998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
inv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(eval(input()))
a = [int(i) for i in readline().split()]

num = [0]*1000001
db = [0]*1000001
for i in a:
    num[i] += i
    db[i] += i*i
    db[i] %= MOD

def zeta(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(n//p,0,-1):
                sieve[k*p] = False
                a[k] += a[k*p]
                a[k] %= MOD
    return a


def meb(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(1,n):
                if k*p >= n: break
                sieve[k*p] = False
                a[k] -= a[k*p] 
                a[k] %= MOD
    return a


#n = 1000000

n = 1000000

#zn = [i*i for i in zeta(num,n)]
#zdb = zeta(db,n)
#print(zn[:20])
#print(zdb[:20])

zn = [i*i for i in zeta(num,n)]
zdb = zeta(db,n)
ans = [i-j for i,j in zip(zn, zdb)]

#ans = [i*i-j for i,j in zip(zeta(num,n), zeta(db,n))]

#print(ans[:20])
#print(meb(ans,n)[:20])

res = 0
for i,c in enumerate(meb(ans,n+1)):
    res = (res + c*inv[i])%MOD
        
print((res*inv[2]%MOD))
# Original solution
# coding: utf-8
# Your code here!
SIZE=1000001; MOD=998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
inv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(eval(input()))
a = [int(i) for i in readline().split()]

num = [0]*1000001
db = [0]*1000001
for i in a:
    num[i] += i
    db[i] += i*i
    db[i] %= MOD

def zeta(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(n//p,0,-1):
                sieve[k*p] = False
                a[k] += a[k*p]
                a[k] %= MOD
    return a


def meb(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(1,n):
                if k*p >= n: break
                sieve[k*p] = False
                a[k] -= a[k*p] 
                a[k] %= MOD
    return a


#n = 1000000

n = 1000000

#zn = [i*i for i in zeta(num,n)]
#zdb = zeta(db,n)
#print(zn[:20])
#print(zdb[:20])

zn = [i*i for i in zeta(num,n)]
zdb = zeta(db,n)
ans = [i-j for i,j in zip(zn, zdb)]

#ans = [i*i-j for i,j in zip(zeta(num,n), zeta(db,n))]

#print(ans[:20])
#print(meb(ans,n)[:20])

res = 0
for i,c in enumerate(meb(ans,n+1)):
    res = (res + c*inv[i])%MOD
        
print((res*inv[2]%MOD))









# Optimized solution
# coding: utf-8
# Your code here!
def Eratosthenes(N): #N以下の素数のリストを返す
    N+=1
    is_prime_list = [True]*N
    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_list[i]:
            is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_list[i]]

#aを破壊的にgcd-zetaする
def zeta_gcd(a,primes):
    n = len(a)-1
    for p in primes:
        for i in range(n//p,0,-1):
            a[i] += a[p*i]
            a[i] %= MOD
#    return a

#aを破壊的にgcd-mobiusする
def mobius_gcd(a,primes):
    n = len(a)
    for p in primes:
        for i in range(1,n):
            if i*p >= n: break
            a[i] -= a[p*i] 
            a[i] %= MOD
#    return a

################################################

#################################################

SIZE=1000001; MOD=998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
inv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD

################################################
#################################################
import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(eval(input()))
a = [int(i) for i in readline().split()]

num = [0]*SIZE
for i in a: num[i] += i

primes = Eratosthenes(SIZE)

zeta_gcd(num,primes)
ans = [i*i for i in num]
mobius_gcd(ans,primes)

res = 0
for i,c in enumerate(ans):
    res = (res + c*inv[i])%MOD
for i in a:
    res = (res-i)%MOD
        
print((res*inv[2]%MOD))
# Original solution
# -*- coding: utf-8 -*-

import sys
import os
import math


N = int(eval(input()))
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def encode(s, alpha, beta):
    t = []
    for c in s:
        if c == ' ':
            t.append(c)
        else:
            gamma = ord(c) - 97
            v = (alpha * gamma + beta) % 26
            w = alphabet[v]
            t.append(w)
    return ''.join(t)


for i in range(N):
    s = input().strip()

    for a in range(26):
        for b in range(26):
            encoded = encode(s, a, b)
            if 'that' in encoded or 'this' in encoded:
                print(encoded)

# Optimized solution
# -*- coding: utf-8 -*-

import sys
import os
import math

N = int(eval(input()))
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def encode(s, alpha, beta):
    t = []
    for c in s:
        if c == ' ':
            t.append(c)
        else:
            gamma = ord(c) - 97
            v = (alpha * gamma + beta) % 26
            w = alphabet[v]
            t.append(w)
    return ''.join(t)


for i in range(N):
    s = input().strip()
    
    for a in range(0, 26):
        for b in range(0, 26):
            encoded_this = encode('this', a, b)
            encoded_that = encode('that', a, b)
            if encoded_this in s or encoded_that in s:
                encoded_alphabet = encode(alphabet, a, b)
                table = str.maketrans(encoded_alphabet, alphabet)
                dst = s.translate(table)
                print(dst)
# Original solution
dict = ["a","b","c","d","e","f","g","h","i","j","k","l","m",\
        "n","o","p","q","r","s","t","u","v","w","x","y","z"]
lsalpha = [1,3,5,7,9,11,15,17,19,21,23,25]

n = int(input())
for roop in range(n):
    code = input()
    for alpha in lsalpha:
        flag = 0
        for beta in range(26):
            decode = ""
            for chara in code:
                if chara != " ":
                    f = dict.index(chara)
                    for i in range(26):
                        if (alpha*i + beta)%26 == f:
                            dechara = dict[i]
                            break
                    decode += dechara
                else:
                    decode += " "
            if decode.count("that") > 0 or decode.count("this") > 0:
                flag = 1
                break
        if flag == 1:
            break
    print(decode)

# Optimized solution
dict = ["a","b","c","d","e","f","g","h","i","j","k","l","m",\
        "n","o","p","q","r","s","t","u","v","w","x","y","z"]
lsalpha = [1,3,5,7,9,11,15,17,19,21,23,25]

def decode(alpha, beta, code):
    msg = ""
    for chara in code:
        if chara != " ":
            f = dict.index(chara)
            for i in range(26):
                if (alpha*i + beta)%26 == f:
                    dechara = dict[i]
                    break
            msg += dechara
        else:
            msg += " "
    return msg
    
n = int(input())
for roop in range(n):
    code = input()
    for alpha in lsalpha:
        flag = 0
        for beta in range(26):
            msg = decode(alpha, beta, code)
            if msg.count("that") > 0 or msg.count("this") > 0:
                flag = 1
                break
        if flag == 1:
            break
    print(msg)
# Original solution
A2Z="abcdefghijklmnopqrstuvwxyz"

def decode(L1,L2,msg):
    x=[]
    for c in msg:
        if 'a'<=c<='z':
            c = L2[L1.index(c)]
        x.append(c)
    return "".join(x)
        
def affine(msg, key):
    a,b = key
    L = [A2Z[(i*a+b)%26] for i in range(26)]
    L = "".join(L)
    return decode(A2Z,L,msg)

def rot(msg, a):
    if a==0: return msg
    a = a % 26
    L = A2Z[a:]+A2Z[:a]
    return decode(A2Z,L,msg)

def find(msg):
    c0=ord('t')
    i = 3
    while True:
        x = affine(msg,[i,0])
        a = (c0-ord(x[0]))%26
        x = rot(x,a)
        if x in['this','that']: return [i,a]
        i += 2

n = eval(input())
for i in range(n):
    msg = input()
    for w in msg.split():
        if len(w)==4:
            key = find(w)
            if key!=[]: break
    print(affine(msg,key))

# Optimized solution
A2Z="abcdefghijklmnopqrstuvwxyz"

def decode(L1,L2,msg):
    x=[]
    for c in msg:
        if 'a'<=c<='z':
            c = L2[L1.index(c)]
        x.append(c)
    return "".join(x)
        
def affine(msg, key):
    a,b = key
    L = [A2Z[(i*a+b)%26] for i in range(26)]
    L = "".join(L)
    return decode(A2Z,L,msg)

def rot(msg, a):
    if a==0: return msg
    a = a % 26
    L = A2Z[a:]+A2Z[:a]
    return decode(A2Z,L,msg)

def find(msg):
    c0=ord('t')
    for i in range(26):
        x = affine(msg,[i,0])
        a = (c0-ord(x[0]))%26
        x = rot(x,a)
        if x in['this','that']: return [i,a]
    return []

n = eval(input())
for i in range(n):
    msg = input()
    for w in msg.split():
        if len(w)==4:
            key = find(w)
            if key!=[]: break
    print(affine(msg,key))
# Original solution
import string
A2Z="abcdefghijklmnopqrstuvwxyz"
R=list(range(26))
def decode(msg,L):
    x=""
    for c in msg: x+=(L[A2Z.index(c)] if "a"<=c<="z" else c)
    return x

def affine(msg, a, b):
    L="".join([A2Z[(i*a+b)%26]for i in R])
    s = decode(msg,L)
    return s

def rot(msg, a):
    a = a % 26
    L = A2Z[a:]+A2Z[:a]
    s = decode(msg,L)
    return s

def checkkey(s):
    c0="t"
    for i in R:
        a = 0
        x = affine(s,i,0)
        c = A2Z.index(x[0])
        if c!=19:
            a = (19-c)%26
            x = rot(x,a)
        if x in['this','that']: return i,a
    return -1,-1

n = eval(input())
while n:
    n-=1
    s = input()
    for w in s.split():
        if len(w)==4:
            a,b = checkkey(w)
            if a!=-1: break
    print(affine(s,a,b))

# Optimized solution
A2Z="abcdefghijklmnopqrstuvwxyz"

def affine(msg, a, b):
    s=""
    for c in msg: s+=(A2Z[(A2Z.index(c)*a+b)%26] if "a"<=c<="z" else c)
    return s

def rot(msg, a):
    a = a % 26
    L = A2Z[a:]+A2Z[:a]
    s=""
    for c in msg: s+=(L[A2Z.index(c)] if "a"<=c<="z" else c)
    return s

def checkkey(s):
    c0="t"
    for i in range(26):
        a = 0
        x = affine(s,i,0)
        c = A2Z.index(x[0])
        if c!=19:
            a = (19-c)%26
            x = rot(x,a)
        if x in['this','that']: return i,a
    return -1,-1

n = eval(input())
while n:
    n-=1
    s = input()
    for w in s.split():
        if len(w)==4:
            a,b = checkkey(w)
            if a!=-1: break
    print(affine(s,a,b))
# Original solution
D = [[-1,0],[0,1],[1,0],[0,-1]]
def s(N):
    used = [[False]*N+[True] for _ in range(N)]+[[True]*(N+1)]
    ret = [[" "]*N for _ in range(N)]
    q = [(0,N-1,0)]
    used[N-1][0] = used[N-1][1] = True
    while len(q) != 0:
        d,y,x = q.pop(0)
        ret[y][x] = "#"
        sy,sx = D[d]
        ry,rx = D[(d+1)%4]
        if not used[y+sy][x+sx]:
            q.append((d,y+sy,x+sx))
            used[y+sy][x+sx] = used[y+ry][x+rx] = True
        elif not used[y+ry][x+rx]:
            q.append(((d+1)%4,y+ry,x+rx))
            used[y+ry][x+rx] = True
    return ret

n = eval(input())
while True:
    n -= 1
    N = eval(input())    
    print("\n".join(["".join(a) for a in s(N)]))
    if n == 0:
        break
    print()

# Optimized solution
D = [[-1,0],[0,1],[1,0],[0,-1]]
def s(N):
    used = [[False]*N+[True] for _ in range(N)]+[[True]*(N+1)]
    ret = [[" "]*N for _ in range(N)]
    d,y,x = 0,N-1,0
    used[N-1][0] = used[N-1][1] = True
    while True:
        ret[y][x] = "#"
        sy,sx = D[d]
        ry,rx = D[(d+1)%4]
        if not used[y+sy][x+sx]:
            used[y+sy][x+sx] = used[y+ry][x+rx] = True
            d,y,x = d,y+sy,x+sx
        elif not used[y+ry][x+rx]:
            used[y+ry][x+rx] = True
            d,y,x = (d+1)%4,y+ry,x+rx
        else:
            break
    return ret

n = eval(input())
while True:
    n -= 1
    N = eval(input())    
    print("\n".join(["".join(a) for a in s(N)]))
    if n == 0:
        break
    print()
# Original solution
def mincos(n,ab):
    aball=[]
    aball+=[(ab[i][0],i+1,'a') for i in range(n)]
    aball+=[(ab[i][1],i+1,'b') for i in range(n)]
    aball.sort()
    
    ans1=sum([i[0] for i in aball[:n]])
    
    hen=aball[n][0]
    hen2=aball[n+1][0]
    d=[]
    t=None
    hantei=True
    for i,c,mab in aball[:n]:
        if t!=None and t!=mab:
            hantei=False
        if  c in d:
            print(ans1)
            exit()
        d+=[c]
        t=mab

    if hantei:
        print(ans1)
        exit()

    ans2=[]
    for i,c,aorb in aball[:n]:
        if aball[n][1]!=c:
            ans2+=[ans1-i+hen]
        else:
            ans2+=[ans1-i+hen2]
    print((min(ans2)))
    exit()

n=int(eval(input()))
print((mincos(n,[list(map(int,input().split())) for i in range(n)])))

# Optimized solution
def mincos(n,ab):
    aball=[]
    aball+=[(ab[i][0],i+1,'a') for i in range(n)]
    aball+=[(ab[i][1],i+1,'b') for i in range(n)]
    aball.sort()
    
    ans1=sum([i[0] for i in aball[:n]])

    hen=aball[n][0]
    hen2=aball[n+1][0]
    d=set()
    t=None
    hantei=True
    for i,c,mab in aball[:n]:
        if t!=None and t!=mab:
            hantei=False
        if  c in d:
            print(ans1)
            exit()
        d.add(c)
        t=mab

    if hantei:
        print(ans1)
        exit()

    ans2=[]
    for i,c,aorb in aball[:n]:
        if aball[n][1]!=c:
            ans2+=[ans1-i+hen]
        else:
            ans2+=[ans1-i+hen2]
    print((min(ans2)))
    exit()

n=int(eval(input()))
print((mincos(n,[list(map(int,input().split())) for i in range(n)])))
# Original solution
import sys,random

input=sys.stdin.readline

N=int(eval(input()))
A=[-1]*N;B=[-1]*N
for i in range(N):
    A[i],B[i]=list(map(int,input().split()))

ans=min(sum(A),sum(B))

temp=[(A[i],i) for i in range(N)]+[(B[i],i) for i in range(N)]
temp.sort()
#print(temp)
data=[0]*N
for i in range(N):
    val,id=temp[i]
    data[id]+=1
S=sum(temp[i][0] for i in range(N))

for i in range(N):
    if data[i]==2:
        test=S
        ans=min(ans,test)
    elif data[i]==1:
        if temp[N-1][1]!=i:
            test=S+max(A[i],B[i])-temp[N-1][0]
        else:
            test=S+max(A[i],B[i])-temp[N-2][0]
        ans=min(ans,test)

print(ans)


# Optimized solution
import sys;input=sys.stdin.readline;N=int(eval(input()));A=[-1]*N;B=[-1]*N
for i in range(N):
    A[i],B[i]=list(map(int,input().split()))
ans=min(sum(A),sum(B));temp=[(A[i],i) for i in range(N)]+[(B[i],i) for i in range(N)];temp.sort();data=[0]*N
for i in range(N):data[temp[i][1]]+=1
S=sum(temp[i][0] for i in range(N))
if max(data)==2:
    print(S)
else:
    for i in range(N):ans=min(ans,S+max(A[i],B[i])-temp[N-1-(temp[N-1][1]==i)][0]);
    print(ans)