CodeEff/ECCO huggingface dataset:
# Original solution
N, Q = list(map(int, input().split()))
query = []
for i in range(Q):
    v, w = list(map(int, input().split()))
    if v < w:
        v, w = w, v
    query.append((v - 1, w - 1))


def f(v, w):
    a=w
    b=v
    s=0
    t=0
    while w != 0:
        w = (w - 1) // N
        s+=1
    while v != 0:
        v = (v - 1) // N
        t+=1
    u=t-s
    while u>0:
        b = (b - 1) // N        
        u-=1
    while a!=b:
        b = (b - 1) // N            
        a = (a - 1) // N  
    return a+1
for v, w in query:
    print((f(v, w)))




# Optimized solution
import sys
N, Q = list(map(int, input().split()))
query = []
for i in range(Q):
    v, w = list(map(int, input().split()))
    if v < w:
        v, w = w, v
    query.append((v - 1, w - 1))


def f(v, w):
    L = set()
    L.add(0)
    while w != 0:
        L.add(w)
        w = (w - 1) // N
    while v != 0:
        if v in L:
            return v + 1
        v = (v - 1) // N
    return 1

if N==1:
    for v, w in query:
        print((w+1))
    sys.exit()
for v, w in query:
    print((f(v, w)))
# Original solution
import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
for i in range(q):
    u,v=list(map(int,input().split()))
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(((u-1)//n)-1)//n
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(((v-1)//n)-1)//n
            else:
                v=(v-1)//n
    print((u+1))


# Optimized solution
import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
for i in range(q):
    u,v=list(map(int,input().split()))
    if n==1:
        print((min(u,v)))
        continue
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(((u-1)//n)-1)//n
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(((v-1)//n)-1)//n
            else:
                v=(v-1)//n
    print((u+1))
# Original solution
from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = list(map(int, readline().split()))
c = 1
B = [1]
ans = []
append = ans.append
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = list(map(int, readline().split()))
    lv = bisect(B, v)
    lw = bisect(B, w)
    if lv < lw:
        w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
    while v != w:
        v = (v + (N - 2)) // N
        w = (w + (N - 2)) // N
    append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")


# Optimized solution
from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = list(map(int, readline().split()))
ans = []
if N == 1:
    for q in range(Q):
        v, w = list(map(int, readline().split()))
        ans.append(str(v))
else:
    c = 1
    B = [1]
    while c < 10**9:
        B.append(c+1)
        c = c*N + 1
    for q in range(Q):
        v, w = list(map(int, readline().split()))
        lv = bisect(B, v)
        lw = bisect(B, w)
        if lv < lw:
            w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
        while v != w:
            v = (v + (N - 2)) // N
            w = (w + (N - 2)) // N
        ans.append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")
# Original solution
from bisect import bisect
from itertools import accumulate


def solve(v, w):
    vl = bisect(table, v)
    wl = bisect(table, w)
    if vl > wl:
        for i in range(vl - wl):
            v = (v + m) // n
    elif wl < vl:
        for i in range(wl - vl):
            w = (w + m) // n
    while v != w:
        if v > w:
            v, w = w, v
        w = (w + m) // n
    return v


n, q = list(map(int, input().split()))
m = n - 2
table, k = [], 1
while True:
    table.append(k)
    k *= n
    if k > 1e9:
        break
table = list(accumulate(table))

print(('\n'.join(map(str, (solve(*list(map(int, input().split()))) for _ in range(q))))))


# Optimized solution
n, q = list(map(int, input().split()))

if n == 1:
    def solve(v, w):
        return min(v, w)
else:
    def solve(v, w):
        while v != w:
            if v > w:
                v, w = w, v
            w = (w + n - 2) // n
        return v

print(('\n'.join(map(str, (solve(*list(map(int, input().split()))) for _ in range(q))))))
# Original solution
def main():
    n,m=list(map(int,input().split()))
    ab=[list(map(int,input().split())) for _ in [0]*m]
    if n==1:
        for a,b in ab:
            print((min(a,b)))
        return
    for a,b in ab:
        while a!=b:
            a,b=min(a,b),max(a,b)
            b=(b+n-2)//n
        print(a)
    
main()

# Optimized solution
def main():
    n,m=list(map(int,input().split()))
    ab=[list(map(int,input().split())) for _ in [0]*m]
    if n==1:
        for a,b in ab:
            print((min(a,b)))
        return
    for a,b in ab:
        while a!=b:
            if a<b:
                b=(b+n-2)//n
            else:
                a=(a+n-2)//n
        print(a)
    
main()
# Original solution
n,q=list(map(int,input().split()))
for i in range(q):
    v,w=list(map(int,input().split()))
    c=[1]
    while v!=1:
        c.append(v)
        v=(v+n-2)//n
    while w not in c:
        w=(w+n-2)//n
    print(w)

# Optimized solution
n,q=list(map(int,input().split()))
for i in range(q):
    v,w=list(map(int,input().split()))
    while v!=w:
        if v>w:
            v=(v+n-2)//n
        else:
            w=(w+n-2)//n
    print(v)
# Original solution
n,q,*t=list(map(int,open(0).read().split()))
for v,w in zip(t[::2],t[1::2]):
  while n>1and v!=w:
    v,w=sorted((v,w))
    w=(w+n-2)//n
  print(v)

# Optimized solution
n,q,*t=list(map(int,open(0).read().split()))
for v,w in zip(t[::2],t[1::2]):
  if n-1:
    while v!=w:
      if v>w:v,w=w,v
      w=(w+n-2)//n
  print(v)
# Original solution
n,q,*t=list(map(int,open(0).read().split()))
for v,w in zip(t[::2],t[1::2]):
 if~-n:
  while v!=w:
   if v>w:v,w=w,v
   w=(w+n-2)//n
 print(v)

# Optimized solution
n,q,*t=list(map(int,open(0).read().split()))
for v,w in zip(t[::2],t[1::2]):
 while n>1and v!=w:
  if v>w:v,w=w,v
  w=(w+n-2)//n
 print(v)
# Original solution
n, a, b = list(map(int, input().split()))
pre_h = [int(eval(input())) for _ in range(n)]

minimum = (min(pre_h) - 1) // a + 1

h = [0] * n
while True:
	for i in range(n):
		if pre_h[i] - b * minimum > 0:
			h[i] = pre_h[i] - b * minimum
		else:
			h[i] = 0

	if sum([(i - 1) // (a - b) + 1 for i in h]) <= minimum:
		break

	#print(h)
	minimum += 1

print(minimum)

# Optimized solution
n, a, b = list(map(int, input().split()))
pre_h = [int(eval(input())) for _ in range(n)]

def check(cnt):
	h = [0] * n
	for i in range(n):
		if pre_h[i] - b * cnt > 0:
			h[i] = pre_h[i] - b * cnt
		else:
			h[i] = 0

	if sum([(i - 1) // (a - b) + 1 for i in h]) <= cnt:
		return True
	else:
		return False

minimum = 1
maximum = (max(pre_h) - 1) // b + 1

while maximum - minimum > 1:
	if check(minimum + (maximum - minimum) // 2):
		maximum = minimum + (maximum - minimum) // 2
	else:
		minimum = minimum + (maximum - minimum) // 2

print(maximum)
# Original solution
def inpl(): return [int(i) for i in input().split()]

N,A,B = inpl()
C = A-B
h = [int(eval(input())) for _ in range(N)]

ans = -(-sum(h)//((N-1)*B+A))
while True:
    hprime = [h[i]-ans*B for i in range(N) if h[i]-ans*B >0]
    hans = ans    
    for j in hprime:
            hans -= -(-j//C)
    if hans >= 0:
        break
    ans += 1
print(ans)    

# Optimized solution
def inpl(): return [int(i) for i in input().split()]

N,A,B = inpl()
C = A-B
h = [int(eval(input())) for _ in range(N)]

lo = -(-sum(h)//((N-1)*B+A)) -1
hi = sum([-(-i//A) for i in h]) 
while hi - lo > 1:
    me = (hi+lo)//2
    hprime = [h[i]-me*B for i in range(N) if h[i]-me*B >0]    
    hans = 0
    for j in hprime:
            hans += -(-j//C)
    if hans <= me:
        hi = me
    else:
        lo = me
print(hi)
# Original solution
import bisect
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def ceil(x):
    return int((-x)//1*(-1))


N, A, B = list(map(int, input().split()))
hp = [int(eval(input())) for _ in range(N)]
diff = A-B


def solve1():
    HP = sorted(hp, reverse=True)
    cnt = 0
    while HP:
        HP = list([x-B for x in HP])
        HP[0] -= A-B
        HP = list([x for x in HP if x > 0])
        HP = sorted(HP, reverse=True)
        cnt += 1
        print(HP)
    print(cnt)


def check(x, HP):
    cnt = 0
    for i in range(N):
        if HP[i]-B*x <= 0:
            break
        else:
            cnt += ceil((HP[i]-B*x)/diff)
    #print("x->", x)
    # print(cnt)
    #print(cnt <= x)
    return cnt <= x


def solve2():
    HP = sorted(hp, reverse=True)
    mi = HP[0]//A
    ma = ceil(HP[0]/B)
    #print("mi,ma->", mi, ma)
    while mi <= ma:
        mid = (mi+ma)//2
        if check(mid, HP):
            ma = mid-1
        else:
            mi = mid+1
    print(mi)


solve2()


# Optimized solution
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def ceil(x):
    return int((-x)//1*(-1))


N, A, B = list(map(int, input().split()))
hp = [int(eval(input())) for _ in range(N)]
diff = A-B


def check(x, HP):
    cnt = 0
    for i in range(N):
        if HP[i]-B*x <= 0:
            break
        else:
            cnt += ceil((HP[i]-B*x)/diff)
    return cnt <= x


def solve2():
    HP = sorted(hp, reverse=True)
    mi = HP[0]//A
    ma = ceil(HP[0]/B)
    while mi <= ma:
        mid = (mi+ma)//2
        if check(mid, HP):
            ma = mid-1
        else:
            mi = mid+1
    print(mi)


solve2()
# Original solution
import math

N, A, B = list(map(int, input().split()))

h = []
min_h = 10 ** 10
max_h = 0
for _ in range(N):
    hi = int(eval(input()))
    if hi < min_h:
        min_h = hi
    if hi > max_h:
        max_h = hi
    h.append(hi)
    
min_K = math.ceil(min_h / A)
max_K = math.ceil(max_h / B)
K = min_K
while(min_K != max_K):
    x = [math.ceil((n - K * B) / (A - B)) for n in h]
    sum_x = sum([xi for xi in x if xi > 0])
    if sum_x <= K:
        max_K = K
        K = math.floor((min_K + K) / 2)
    else:
        min_K = K + 1
        K = math.floor((K + max_K) / 2) + 1

print(min_K)

# Optimized solution
import math

N, A, B = list(map(int, input().split()))

h = []
min_h = 10 ** 10
max_h = 0
for _ in range(N):
    hi = int(eval(input()))
    if hi < min_h:
        min_h = hi
    if hi > max_h:
        max_h = hi
    h.append(hi)
    
min_K = math.ceil(sum(h) / (A - B + B * N)) - 1
max_K = math.ceil(max(h) / A) * N
min_K = math.ceil(min_h / A)
max_K = math.ceil(max_h / B)
K = min_K
while(min_K != max_K):
    x = [math.ceil((n - K * B) / (A - B)) for n in h]
    sum_x = sum([xi for xi in x if xi > 0])
    if sum_x <= K:
        max_K = K
        K = math.floor((min_K + K) / 2)
    else:
        min_K = K + 1
        K = math.floor((K + max_K) / 2) + 1

print(K)
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# from numpy import array, sum

N, A, B = list(map(int, input().split()))

h_li = []

for i in range(N):
	h_li.append(int(eval(input())))

def all_beatable_check(k):
	# All enemy get B damage every time
	h_damaged = [h - B*k for h in h_li]
	# print(h_damaged)
	# A-B damage will be additionally given to enemies s.t. HP > 0
	ex_dmg = A - B
	h_ex_needed = [(h+ex_dmg-1) // ex_dmg if h > 0 else 0 for h in h_damaged]
	# print(h_ex_needed)
	# how many A-B damage is needed to beat all enemies
	hits_needed = sum(h_ex_needed)
	if hits_needed > k:
		return False
	else:
		return True

MIN_K = 0         # impossible
MAX_K = max(h_li) # possible

while MAX_K - MIN_K > 1:
	# print(f"{MIN_K}-{MAX_K} {MIN_K + (MAX_K - MIN_K) // 2}")
	k = MIN_K + (MAX_K - MIN_K) // 2
	res = all_beatable_check(k)
	if res is True:
		MAX_K = k
	elif res is False:
		MIN_K = k

print(MAX_K)

# Optimized solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# from numpy import array, sum

N, A, B = list(map(int, input().split()))

h_li = []

for i in range(N):
	h_li.append(int(eval(input())))

def all_beatable_check(k):
	# All enemy get B damage every time
	h_damaged = [h - B*k for h in h_li]
	# print(h_damaged)
	# A-B damage will be additionally given to enemies s.t. HP > 0
	ex_dmg = A - B
	h_ex_needed = [(h+ex_dmg-1) // ex_dmg if h > 0 else 0 for h in h_damaged]
	# print(h_ex_needed)
	# how many A-B damage is needed to beat all enemies
	hits_needed = sum(h_ex_needed)
	if hits_needed > k:
		return False
	else:
		return True

MIN_K = 0         # impossible
MAX_K = max(h_li) # possible

while MAX_K - MIN_K > 1:
	# print(f"{MIN_K}-{MAX_K} {MIN_K + (MAX_K - MIN_K) // 2}")
	k = (MIN_K + MAX_K) // 2
	res = all_beatable_check(k)
	if res is True:
		MAX_K = k
	elif res is False:
		MIN_K = k

print(MAX_K)
# Original solution
import math

n, a, b = list(map(int, input().split()))
hs = list(map(int, (eval(input()) for _ in range(n))))

m = sum(hs) // (a + (n-1)*b) - 10
M = sum(math.ceil(h/a) for h in hs)

def killable(p, hs, a, b):
    x = sum(max(0, math.ceil((h-p*b) / (a-b))) for h in hs)
    return x <= p

while(m+1 < M):
    c = (m+M) // 2
    if killable(c, hs, a, b):
        M = c
    else:
        m = c
print(M)

# Optimized solution
import math

n, a, b = list(map(int, input().split()))
hs = list(map(int, (eval(input()) for _ in range(n))))

m = sum(hs) // (a + (n-1)*b) - 1
#M = sum(math.ceil(h/a) for h in hs)
M = max(hs) // b + 1

def killable(p, hs, a, b):
    x = sum(max(0, math.ceil((h-p*b) / (a-b))) for h in hs)
    return x <= p

while(m+1 < M):
    c = (m+M) // 2
    if killable(c, hs, a, b):
        M = c
    else:
        m = c
print(M)
# Original solution
# -*- coding: utf-8 -*-
from bisect import bisect
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(eval(input())))

x = sum(H) // (A+B*(N-1))
H = sorted(H)
 
while len(H):
    nH = [h - B*x for h in H]
    i = bisect(nH, 0)
    nH = nH[i:]
    H = H[i:]
    if sum([h//D + (h%D>0) for h in nH]) <= x:
        print(x)
        break
    else:
        x = max(x+1, sum(H) // (A+B*(N-1)))

# Optimized solution
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(eval(input())))

H = sorted(H)
l = sum(H) // (A+B*(N-1))
r = sum([h//A + (h%A>0) for h in H])

def judge(m):
    nH = [h - B*m for h in H]
    if sum([h//D + (h%D>0) for h in nH if h > 0]) <= m:
        return True
    else:
        return False

while r-l > 1:
    mid = (l+r)//2
    if judge(mid):
        r = mid
    else:
        l = mid
if judge(l):
    print(l)
else:
    print(r)
# Original solution
n, a, b = list(map(int, input().split()))
h = [int(eval(input())) for i in range(n)]
h.sort()

def check(k):
    top = 0
    tmp = h[::]
    for i in range(n):
        amari = tmp[i] - b*k
        if amari > 0:
            top += -(-amari//(a-b))
    return top <= k

# 二分探索
left = 0
right = -(-1*sum(h)//b)
while(right-left>1):
    next_ind = (left + right)//2
    if check(next_ind):
        right = next_ind
    else:
        left = next_ind
print(right)

# Optimized solution
n, a, b = list(map(int, input().split()))
h = [int(eval(input())) for i in range(n)]

def check(k):
    cnt = 0
    for i in h:
        hp = i - k*b
        if hp > 0:
            cnt += -(-hp//(a-b))
    return cnt <= k

left = 0
right = 10**10
while right - left>1:
    mid = (right + left)//2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)
# Original solution
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = input()
    if S == '0':
        break
    m = {}
    for i in range(11):
        m[i] = []
    m[0].append(11)
    diff = 0
    even = True
    S = reversed(S)
    for c in S:
        num = int(c)
        if even:
            diff += num
        else:
            diff -= num
        diff %= 11
        m[diff].append(num)
        even = (not even)
    ans = 0
    #print m
    for i in range(11):
        lst = m[i]
        for i in range(len(lst)):
            if lst[i] != 0:
                ans += i
    
    print(ans)


# Optimized solution
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = input()
    if S == '0':
        break
    m = [0 for i in range(11)]
    m[0] = 1
    diff = 0
    even = True
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        if even:
            diff += num
        else:
            diff -= num
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even = (not even)
    
    print(ans)
# Original solution
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = input()
    if S == '0':
        break
    m = [0 for i in range(11)]
    m[0] = 1
    diff = 0
    even = True
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        if even:
            diff += num
        else:
            diff -= num
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even = (not even)
    
    print(ans)


# Optimized solution
while True:
    S = input()
    if S == '0':
        break
    m = [0 for i in range(11)]
    m[0] = 1
    diff = 0
    even = True
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        if even:
            diff += num
        else:
            diff -= num
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even = (not even)
    
    print(ans)
# Original solution
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = input()
    if S == '0':
        break
    m = [1] + [0 for i in range(10)]
    diff = 0
    even = 1
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        diff += num * even
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even *= -1
    print(ans)


# Optimized solution
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = input()
    if S == '0':
        break
    m = [1] + [0 for i in range(10)]
    diff = ans = 0
    even = 1
    S = reversed(S)
    for c in S:
        num = int(c)
        diff = (diff + num * even) % 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even *= -1
    print(ans)
# Original solution
while True:
 S=input()
 if S=='0':break
 m=[1]+[0 for i in range(10)]
 d=A=0
 e=1
 S=reversed(S)
 for c in S:
  d=(d+int(c)*e)%11  
  if int(c)!=0:A+=m[d]
  m[d]+=1
  e*=-1
 print(A)


# Optimized solution
while True:
    S = input()[::-1]
    if S == '0' : break
    m = [1] + [0] * 10
    diff = ans = 0
    even = 1
    for c in S:
        num = int(c)
        diff = (diff + num * even) % 11
        if num : ans += m[diff]
        m[diff] += 1
        even *= -1
    print(ans)
# Original solution
import sys
sys.setrecursionlimit(10**9)

N = int(eval(input()))
As = list(map(int, input().split()))
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = list(map(int, input().split()))
    adjL[A-1].append(B-1)
    adjL[B-1].append(A-1)

def dfsTree(vNow):
    useds[vNow] = True
    for v2 in adjL[vNow]:
        if not useds[v2]:
            chlds[vNow].append(v2)
            dfsTree(v2)

vRoot = 0
chlds = [[] for v in range(N)]
useds = [False] * N
dfsTree(vRoot)

def dfs(vNow):
    if not chlds[vNow]:
        return As[vNow]
    cs = []
    for chld in chlds[vNow]:
        c = dfs(chld)
        if c == -1:
            return -1
        cs.append(c)
    sumC = sum(cs)
    T = 2*As[vNow] - sumC
    L = sumC - As[vNow]
    if T < 0 or L < 0:
        return -1
    if min(sumC-max(cs), sumC//2) >= L:
        return T
    else:
        return -1

ans = dfs(vRoot)
isLeaf = len(chlds[vRoot]) == 1
if (isLeaf and ans == As[vRoot]) or (not isLeaf and ans == 0):
    print('YES')
else:
    print('NO')


# Optimized solution
import sys
sys.setrecursionlimit(10**9)

N = int(eval(input()))
As = list(map(int, input().split()))
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = list(map(int, input().split()))
    adjL[A-1].append(B-1)
    adjL[B-1].append(A-1)

def dfsTree(vNow):
    useds[vNow] = True
    for v2 in adjL[vNow]:
        if not useds[v2]:
            chlds[vNow].append(v2)
            dfsTree(v2)

vRoot = 0
chlds = [[] for v in range(N)]
useds = [False] * N
dfsTree(vRoot)

def dfs(vNow):
    if not chlds[vNow]:
        return As[vNow]
    cs = []
    for chld in chlds[vNow]:
        c = dfs(chld)
        if c == -1:
            return -1
        cs.append(c)
    sumC = sum(cs)
    T = 2*As[vNow] - sumC
    if T < 0:
        return -1
    cs.append(T)
    sumC += T
    if max(cs) <= sumC/2:
        return T
    else:
        return -1

ans = dfs(vRoot)
isLeaf = len(chlds[vRoot]) == 1
if (isLeaf and ans == As[vRoot]) or (not isLeaf and ans == 0):
    print('YES')
else:
    print('NO')
# Original solution
while True:
    n = eval(input())
    if n == 0: break
    P = set(tuple(map(int, input().split())) for i in range(n))
    ans = 0
    for xi, yi in P:
        for xj, yj in P:
            q = (xj - yj + yi, yj + xj - xi)
            r = (xi - yj + yi, yi + xj - xi)
            if q in P and r in P:
                ans = max(ans, pow(xi - xj, 2) + pow(yi - yj, 2))
    print(ans)

# Optimized solution
while True:
    n = eval(input())
    if n == 0: break
    P = set(tuple(map(int, input().split())) for i in range(n))
    ans = 0
    for xi, yi in P:
        for xj, yj in P:
            q = (xj - yj + yi, yj + xj - xi)
            r = (xi - yj + yi, yi + xj - xi)
            if q in P and r in P:
                ans = max(ans, (xi - xj) ** 2 + (yi - yj) ** 2)
    print(ans)
# Original solution
while True:
    n = eval(input())
    if n == 0: break
    P = set(tuple(map(int, input().split())) for i in range(n))
    ans = 0
    for xi, yi in P:
        for xj, yj in P:
            q = (xj - yj + yi, yj + xj - xi)
            r = (xi - yj + yi, yi + xj - xi)
            if q in P and r in P:
                ans = max(ans, (xi - xj) ** 2 + (yi - yj) ** 2)
    print(ans)

# Optimized solution
while True:
    n = eval(input())
    if n == 0: break
    P = [(list(map(int, input().split()))) for i in range(n)]
    S = set(map(tuple, P))
    ans = 0
    for i in range(n - 1):
        xi, yi = P[i]
        for j in range(i + 1, n):
            xj, yj = P[j]
            q = (xj - yj + yi, yj + xj - xi)
            r = (xi - yj + yi, yi + xj - xi)
            if q in S and r in S:
                ans = max(ans, (xi - xj) ** 2 + (yi - yj) ** 2)
    print(ans)