Harryxun/stf_run huggingface dataset:
from fractions import gcd
N = int(input())
arr = []

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


for i in range(N):
    arr.append(list(map(int, input().split())))

C = []
for i in range(N):
    for j in range(N):
        if i < j:
            x = arr[i][0]-arr[j][0]
            y = arr[i][1]-arr[j][1]
            g = gcd(x, y)
            x = int(x / g)
            y = int(y / g)
            C.append([x, y])

C = get_unique_list(C)
S = [0 for i in range(len(C))]

for c in range(len(C)):
    tmp = [[arr[0][0], arr[0][1]]]
    for i in range(1, N):
        l = len(tmp)
        for j in range(l):
            if (tmp[j][0] - arr[i][0])%C[c][0] == 0 and (tmp[j][1] - arr[i][1])%C[c][1] == 0:
                pass
            else:
                tmp.append([arr[i][0], arr[i][1]])
    S[c] = len(tmp)

print(min(S))


### FIXED CODE ###

import sys
N = int(input())
arr = []

for i in range(N):
    arr.append(list(map(int, input().split())))

if N == 1:
    print(1)
    sys.exit()

d = {}

for i in range(N):
    for j in range(N):
        if i != j:
            x = arr[i][0] - arr[j][0]
            y = arr[i][1] - arr[j][1]
            if (x, y) in list(d.keys()):
                d[(x, y)] += 1
            else:
                d[(x, y)] = 1

print(N - max(list(d.values())))
n , m = map(int, input().split())
a = list(map(int,input().split()))
a.sort()
x=[]
for i in range(m):
    b , c = map(int, input().split())
    x+=[c]*b
x.sort(reverse=True)
for i in range(n):
    if a[i]>=x[i]:
        t=i
        break
a=x[:t]+a[t:]
print(sum(a))


### FIXED CODE ###

n , m = map(int, input().split())
a = list(map(int,input().split()))
a.sort()
bc=[]
for i in range(m):
    b , c = map(int, input().split())
    bc.append((b,c))
bc.sort(key = lambda x : x[1],reverse=True)

t=0
for i in range(m):
    b,c=bc[i]
    if t>=n:
        break
    if a[t]>=c:
        break
    for j in range(b):
        if a[t]<c:
            a[t]=c
            if t<n-1:
                t+=1
        else:
            break
print(sum(a))
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2], A[N//2+1]
    del A[N // 2]
    del A[N // 2]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)



### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A.sort()

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2-1], A[N//2]
    del A[N // 2-1]
    del A[N // 2-1]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)
# x無視したやつが回文なってればいいんじゃね？
# 真ん中にしたい(x以外の)文字が決まれば、もとのsにインデックスを適応して、左右のxの数の差をとればいい
s = input()

t = ""
for sv in s:
    if sv != "x":
        t += sv

if t != t[::-1]:
    print(-1)
    exit()

mid = t[len(t) // 2]
mid_c = t.count(mid) // 2
leftx, rightx = 0, 0
count = 0
for sv in s:
    if sv == "x" and count < mid_c:
        leftx += 1
    elif sv == "x" and mid_c <= count:
        rightx += 1
    elif sv == mid and count < mid_c:
        count += 1

print(abs(rightx - leftx))


### FIXED CODE ###

# x無視したやつが回文なってればいいんじゃね？
# 真ん中にしたい(x以外の)文字が決まれば、もとのsにインデックスを適応して、左右のxの数の差をとればいい
# と思ったけど差をとっただけだと駄目だな xaaxxxbxxcxxxxbxaxxaxx はこの考えだと3だけど実際は7だし
# もうしかたねぇから無理やりsplitした（アホか？）
# これでいけると思いきや駄目 abxxxbaとかでエラーになる
# 趣向を変えて、両脇から比較していくことにしてみる

s = input()
# めんどくさいけどここで確実になるときのやつと回文にならんときのやつを判定すっか
if len(s) == 1:
    print(0)
    exit()
t = ""
for sv in s:
    if sv != "x":
        t += sv
if t != t[::-1]:
    print(-1)
    exit()

l, r = 0, len(s) - 1
ls, rs = "", ""
ans = 0
x = False
while l < r:
    if s[l] == s[r]:
        ls += s[l]
        rs += s[r]
        l += 1
        r -= 1
    else:
        if s[l] == "x":
            while l < r and s[l] != s[r]:
                l += 1
                ans += 1
        else:
            while l < r and s[r] != s[l]:
                r -= 1
                ans += 1
print(ans)
import sys

def main():
	x = sys.stdin.read()
    if x == 7 or x == 5 or x == 3:
      print("YES")
    else:
      print("NO")

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
 
def main():
    x = int(sys.stdin.readline().strip())
    
    if x == 7 or x == 5 or x == 3:
        print("YES")
    else:
        print("NO")
 
if __name__ == "__main__":
    main()
# 前から順番に後ろに向けてswap
n = int(input())
ps = list(map(int, input().split()))

cnt = 0
for i, p in enumerate(ps):
    if i + 1 == p:
        ps[i], ps[i+1] = ps[i+1], ps[i]
        cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
ps = list(map(int,input().split()))
# p_swap = [-1]*N
ans = 0
for i in range(N-1):
    if i+1 == ps[i]:
        p1,p2 = ps[i:i+2]
        ps[i] = p2
        ps[i+1] = p1
        ans += 1
if ps[N-1] == N:
    ans += 1
print(ans)
In [93]: s, w  = map(int,input().split()) 
    ...: print("{} {}".format(s,w)) 
    ...: if s <= w: 
    ...:     print("unsafe") 
    ...: else : 
    ...:     print("safe") 

### FIXED CODE ###

s, w  = map(int,input().split())
if s <= w:
    print("unsafe")
else :
    print("safe")
ct=[]
for i in range(N):
    ct.append(list(map(int, input().strip().split(' '))))
    
tle=True
c=10000

for i in range(N):
    if ct[i][1]<=T:
        tle=False
        c=min(c,ct[i][0])
        
if tle:
    print('TLE')
else:
    print(c)

### FIXED CODE ###

N, T=map(int,input().strip().split(' '))

ct=[]
for i in range(N):
    ct.append(list(map(int, input().strip().split(' '))))
    
tle=True
c=100000000

for i in range(N):
    if ct[i][1]<=T:
        tle=False
        c=min(c,ct[i][0])
        
if tle:
    print('TLE')
else:
    print(c)
K,N=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
dist=[A[0]+K-A[-1]]+[A[i]-A[i-1] for i in range(1,N)]
print(k-max(dist))

### FIXED CODE ###

K,N=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
dist=[A[0]+K-A[-1]]+[A[i]-A[i-1] for i in range(1,N)]
print(K-max(dist))
N = int(input())
K = int(input())
A=[]
for i in range(K):
    d = int(input())
    for i in range(d):
        a = int(input())
        A.append(a)

 
ans = len(list(set(A)))
print(N-ans)

### FIXED CODE ###

N,K = map(int, input().split())
A=[]
for i in range(K):
    d = int(input())
    a=list(map(int, input().split()))
    for i in range(d):
        A.append(a[i])

ans = len(list(set(A)))
print(N-ans)
x=input().split().replace(' ','')
print('H' if x=='HH' or x=='DD' else 'D')

### FIXED CODE ###

x=input().replace(' ','')
print('H' if x=='HH' or x=='DD' else 'D')
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

X, A = map(int, input().split())
if X < A:
    print(0)
else:jprint(10)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

X, A = map(int, input().split())
if X < A:
    print(0)
else:
    print(10)
n=int(input())
A=list(map(int,input().split()))

i=n-1
while i>=0:
	if A[i]==1:
		break
	i-=1

if i==-1:
	print(0)
elif i==0:
	print(1)
	print(1)
else:
	i=(i+1)//2-1
	while i>=0:
		B=[A[j] for j in range(i,n,i+1)]
		r=sum(B[1:])
		
		A[i]=A[i]^r%2
		
		i-=1
		C=[m for m,k in enumerate(A,1) if k!=0]
		print(len(C))
		print(*C)	

### FIXED CODE ###

r = int(input())
print(3*(r**2))
N = int(input())
K = int(input())
 
i = 1
for i in range(N):
    if i >= K:
	i += K
    else:
	i *= 2
print(i)

### FIXED CODE ###

N = int(input())
K = int(input())
 
i = 1
for j in range(N):
    i=min(i*2, i+K)
print(i)
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

#print(lcm(27, 18, 9, 3))
n=int(input())
ab = []
for _ in range(n):
    a= int(input())
    ab.append(a)
print(lcm_list(ab))

### FIXED CODE ###

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

#print(lcm(27, 18, 9, 3))
n=int(input())
ab = []
for _ in range(n):
    a= int(input())
    ab.append(a)
print(lcm(ab))
n = int(input())
a = list(map(int, input()))
print(max(a) - min(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
print(max(a) - min(a))
a = int(input())
b = int(input())
print(a, b)
if a*b%2 == 0:
  print("Even")
elif a*b%2 == 1:
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
print("Even" if a*b % 2 == 0 else "Odd")
s=input()
s=s.split(' ')
maisuu = int(s[0])
maney  = int(s[1])

minn_man = int(maney/10000)

if min_maisuu <= maisuu <= maney/1000:
	minn_go  = maney / 5000 +1
	minn_sen = maney / 1000 +1
	minn_man += 1

	for man in range(0,minn_man):
		for go in range(0,minn_go):
			for sen in range(0,minn_sen):
				if man+go+sen == maisuu:
					if man*10000+ go*5000 + sen*1000 == maney:
						print(str(man)+","+str(go)+","+str(sen))
						flg=False
if flg:
	print('-1,-1,-1')


### FIXED CODE ###

s=input()
s=s.split(' ')
maisuu = int(s[0])
maney  = int(s[1])
 
minn_man = int(maney/10000)+1
minn_go  = int(maney / 5000) +1
for man in range(0,minn_man):
	for go in range(0,minn_go):
		# for sen in range(0,minn_sen):
		sen = maisuu - go - man
		if sen>=0:
			if man*10000+ go*5000 + sen*1000 == maney:
				print(str(man)+" "+str(go)+" "+str(sen))
				exit()
print('-1 -1 -1')
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

ans = 0
for i in range(M):
    ab_list = [[] for i in range(N)]
    for j in range(M):
        if i != j:
            k = ab[j]
            ab_list[k[0] - 1].append(k[1] - 1)
            ab_list[k[1] - 1].append(k[0] - 1)
            
    DFS_list = [0 for j in range(N)]
    DFS_list[i] = 0
    def DFS(v):
        DFS_list[v] = 1
        for j in ab_list[v]:
            if DFS_list[j] == 0:
                DFS(j)
    DFS(i)
    if sum(DFS_list) != N:
        ans += 1
print(ans)

### FIXED CODE ###

def wf(this_graf):
    s = len(graf)
    for k in range(s):
        for i in range(s):
            for j in range(s):
                this_graf[i][j] = min(this_graf[i][j], this_graf[i][k] + this_graf[k][j])
    return this_graf

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
graf = [[10 ** 10 for i in range(n)] for j in range(n)]

for i, j in ab:
    graf[i - 1][j - 1] = 1
    graf[j - 1][i - 1] = 1

import copy
cnt = 0

for i, j in ab:
    this_graf = copy.deepcopy(graf)
    tmp = 0
    this_graf[i - 1][j - 1] = 10 ** 10
    this_graf[j - 1][i - 1] = 10 ** 10
    this_graf = wf(this_graf)
    for i in range(n):
        for j in range(n):
            if this_graf[i][j] == 10 ** 10:
                tmp = 1
                break
        if tmp:
            break
    cnt += tmp

print(cnt)
n=int(input())
a=[int(i) for i in input().split()]
count=0
flag=0
b=[]
for i in range(len(a)-1):
  if(a[i]<=a[i+1]):
    flag=1
    count+=1
  else:
    flag=0
    b.append(count)
    count=0
print(max(b))

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
count=0
flag=0
b=[]
maxi=0
for i in range(len(a)-1):
  if(a[i]>=a[i+1] and flag==0):
      count=1
      flag=1
      
  elif(a[i]>=a[i+1] and flag==1):
    count+=1
    if(maxi<count):
        maxi=count
        
  else:
    count=0
    flag=0
      
print(maxi)
import numpy as np

power = 1
n = int(input())
tmp = 10 ** 9 + 7

for i in range(n):
    power = power * (i + 1)

print(power % tmp)

### FIXED CODE ###

power = 1
n = int(input())
tmp = 10 ** 9 + 7

for i in range(n):
    power = power * (i + 1) % tmp

print(power)
from collections import defaultdict

def prime_factors(n):
    arr = []
    temp = n
    R = int(-(-n**0.5//1))
    furui = [0]*(R+1)
    for i in range(2, R+1):
        if furui[i]:
            continue
        if temp%i == 0:
            while temp%i == 0:
                temp //= i
            arr.append(i)
        m = i
        while m < R+1:
            furui[m] = 1
            m += i

    if temp != 1:
        arr.append(temp)

    return arr

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

nums = defaultdict(int)

for a in A:
    for x in prime_factors(a):
        nums[x] += 1

y = max(nums.values())

if y < 2:
    print('pairwise coprime')
elif y < N:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)

# 素因数テーブルの作成
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

# 素因子をカウント
for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        nums[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y-Ones < N:
    print('setwise coprime')
else:
    print('not coprime')
# ID
n,m=map(int,input().split())
s=[[] for _ in range(m)]
for i in range(m):
    p,y=map(int,input().split())
    s[p-1].append([y,i])

for i in range(len(s)):
    s[i].sort()

ans=[]
for i,ss in enumerate(s):
    for j,sss in enumerate(ss):
        if ss:
            if sss:
                id_no=''
                id_no+='0'*(6-len(str(i+1)))+str(i+1)
                id_no+='0'*(6-len(str(j+1)))+str(j+1)
                s[i][j].append(id_no)

for i,ss in enumerate(s):
    for j,sss in enumerate(ss):
        ans.append(s[i][j])
ans.sort(key=lambda x:x[1])
for aa in ans:
    print(aa[2])

### FIXED CODE ###

n, m = map(int, input().split())
py = []
for _ in range(m):
  py.append(list(map(int,input().split())) + [0])

sortPy = sorted(py, key = lambda x : (x[0], x[1]))
 
d = {}
for i, (p, y, n) in enumerate(sortPy):
  if p in d:
    d[p] += 1
  else:
    d[p] = 1
  sortPy[i][2] = d[p]

for p, y, n in py:
  print(str(p).zfill(6) + str(n).zfill(6))
n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)
A = [0] * (n+1)
B = [0] * (n+1)
P = [0] * (q+1)
X = [0] * (q+1)
for i in range(1,n):
    A[i],B[i] = [int(j) for j in input().split()]
for i in range(1,q+1):
    P[i],X[i] = [int(j) for j in input().split()]

NIL = -1

class node:
    def __init__(self):
        self.value = 0
        self.child = []
        self.parent = NIL

def childadd(T,x):
    for i in range(len(T[x].child)):
        T[T[x].child[i]].value += T[x].value
        if T[T[x].child[i]].child != []:
            childadd(T,T[x].child[i])


T[1] = node()
T[1].parent = 0
for i in range(1,n):
    if T[A[i]].parent != NIL:
        T[B[i]] = node()
        T[A[i]].child.append(B[i])
        T[B[i]].parent = T[A[i]]
    else:
        T[A[i]] = node()
        T[B[i]].child.append(A[i])
        T[A[i]].parent = T[B[i]]

for i in range(1,q+1):
    T[P[i]].value += X[i]

childadd(T,1)

for i in range(1,n+1):
    print(T[i].value,end = " ")


### FIXED CODE ###

from collections import deque

n,q = input().split()
n = int(n)
q = int(q)
T = [0] * (n+1)

to = [[] for i in range(n+1)]
cnt = [0] * (n)
for i in range(1,n):
    a,b = [int(j) for j in input().split()]
    to[a].append(b)
    to[b].append(a)
for i in range(1,q+1):
    P,X = [int(j) for j in input().split()]
    T[P] += X
NIL = -1

q =deque()
q.append((1,0,NIL))
while len(q)>0:
    p,x,prev = q.pop()
    x += T[p]
    cnt[p-1] = x
    for i in to[p]:
        if i != prev:
            q.append((i,x,p))
print(*cnt)
a,b,c,d=input()
x=int(a+b)
y=int(c+d)
if 0<=x<=12 and 1<=y<=12:
  print('AMBIGUOUS')
elif 1<=x<=12 and 0<=y=12:
  print('AMBIGUOUS')
elif 0<=x<=99 and 1<=y<=12:
  print('YYMM')
elif 1<=x<=12 and 0<=y<=99:
  print('MMYY')
else:
  print('NA')

### FIXED CODE ###

a,b,c,d=input()
x=int(a+b)
y=int(c+d)
if 1<=x<=12 and 1<=y<=12:
  print('AMBIGUOUS')
elif 1<=x<=12 and 1<=y<=12:
  print('AMBIGUOUS')
elif 0<=x<=99 and 1<=y<=12:
  print('YYMM')
elif 1<=x<=12 and 0<=y<=99:
  print('MMYY')
else:
  print('NA')
import itertools as tool

N, K = map(int, input().split())
a = [int(x) for x in input().split()]

beautifuls = []
for i in range(0, len(a)):
    for j in range(i+1, len(a)+1):
        beautiful = sum(a[i:j])
        beautifuls.append(beautiful)

beau_K = list(tool.combinations(beautifuls, K))
ands = []
for combi in beau_K:
    for i in range(K):
        if i == 0:
            tmp = combi[0]
        else:
            tmp = bin(tmp & combi[i])
    ands.append(eval(str(tmp)))
print(max(ands))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
a = LIST()

l = []

for i in range(1, N+1):
	tmp = sum(a[:i])
	for j in range(N-i+1):
		l.append(tmp)
		tmp -= a[j]
		if j+i <= N-1:
			tmp += a[j+i]

ans = 0
for i in range(max(l).bit_length()-1, -1, -1):
	nextl = []
	for x in l:
		if (x>>i)&1:
			nextl.append(x)
	if len(nextl) >= K:
		ans += 1<<i
		l = nextl
print(ans)
N=int(input())
for i in range(1,10):
  if n/i==n//i<10:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

import sys
 
N=int(input())
for i in range(1,10):
  if N/i==N//i  and N/i<10:
    print("Yes")
    sys.exit()
print("No")
import fractions
 
a,b = map(int,input().split())
g = fractions.gcd(a,b)
 
ans=[1]
p=2
while g != 1:
    if g%p == 0:
        ans.append(p)
        g = g//p
    else:
        p += 1
 
print(len(set(ans)))


### FIXED CODE ###

N=int(input())
a=(N-1)//2 + 1
print(a/N)
from collections import defaultdict

N,P=map(int,input().split())
S=input()

def solMin():
  dp=[[0]*P for i in range(N+1)]
  
  for i,s in enumerate(map(int,S), start=1):
    dp[i][s%P]+=1
    for p in range(P):
      dp[i][(p*10+s)]+=dp[i-1][p]
  
  return sum(dp[i][0] for i in range(N+1))

def solLarge():
  cnt=defaultdict(int)
  ret=0
  now=0
  
  for d,s in enumerate(map(int, S[::-1])):
    now+=pow(10,d,P)*s
    now%=P
    ret+=cnt[(now-P)%P]
    if now==0:
      ret +=1
    cnt[now]+=1
  
  return ret

print(solMin() if P*N<=10**6 else solLarge())  

### FIXED CODE ###

from collections import defaultdict

N,P=map(int,input().split())
S=input()

def solMin():
  dp=[[0]*P for i in range(N+1)]
  
  for i,s in enumerate(map(int,S), start=1):
    dp[i][s%P]+=1
    for p in range(P):
      dp[i][(p*10+s)%P]+=dp[i-1][p]
  
  return sum(dp[i][0] for i in range(N+1))

def solLarge():
  cnt=defaultdict(int)
  ret=0
  now=0
  
  for d,s in enumerate(map(int, S[::-1])):
    now+=pow(10,d,P)*s
    now%=P
    ret+=cnt[(now-P)%P]
    if now==0:
      ret +=1
    cnt[now]+=1
  
  return ret

print(solMin() if P*N<=10**6 else solLarge())
x,y=map(int,input().split())
if 2*x<=y and y<=4*x and y&2=0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x,y=map(int,input().split())
if 2*x<=y and y<=4*x and y%2==0:
  print("Yes")
else:
  print("No")
from scipy.sparse.csgraph import johnson
import sys
input = sys.stdin.readline

def solve():
  minf = -1*float("inf")
  n,m,l = (int(i) for i in input().split())
  path = [[minf]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    path[a-1][b-1] = c
  d = johnson(path,directed=False)
  q = int(input())
  
  minipath = [[None]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if d[i][j] <= l:
        minipath[i][j] = 1
      else:
        minipath[i][j] = minf
  d2 = johnson(minipath,directed=False)

  for i in range(q):
    s,t = (int(i) for i in input().split())
    s,t = s-1,t-1
    cost = d2[s][t]
    if cost == minf:
      print(-1)
    else:
      print(int(cost)-1)

solve()

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline
def solve():
  inf = float("Inf")
  n,m,l = (int(i) for i in input().split())
  path = [[-1*inf]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    path[a-1][b-1] = c
    path[b-1][a-1] = c
  d = floyd_warshall(path)
  q = int(input())
  minipath = [[-1*inf]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if d[i][j] <= l:
        minipath[i][j] = 1
  d2 = floyd_warshall(minipath)

  for i in range(q):
    s,t = (int(i) for i in input().split())
    s,t = s-1,t-1
    cost = d2[s][t]
    if cost == inf:
      print(-1)
    else:
      print(int(cost)-1)

solve()
Imp = input().split()
A = Imp[0]
B = Imp[1]
re = 0
if A % 3 == 0:    
    re = 1
if B % 3 == 0:
    re = 1
if (A+B) % 3 == 0:
        re = 1
        
if re ==1:
    print("Possible")
else:
    print("Impossible")

### FIXED CODE ###

Imp = list(map(int, input().split()))
A = Imp[0]
B = Imp[1]
re = 0
if A % 3 == 0:    
    re = 1
if B % 3 == 0:
    re = 1
if (A+B) % 3 == 0:
        re = 1
        
if re ==1:
    print("Possible")
else:
    print("Impossible")
import string

alphabets = {k:0 for k in string.ascii_lowercase}

for c in input().lower():
  if c == ' ':
    continue
  alphabets[c] += 1

for c, n in sorted(alphabets.items()):
  print("{} : {}".format(c, n))

### FIXED CODE ###

import string

alphabets = {k:0 for k in string.ascii_lowercase}

while True:
  try:
    for c in input().lower():
      if alphabets.get(c) is None:
        continue
      alphabets[c] += 1
  except:
    break
for c, n in sorted(alphabets.items()):
  print("{} : {}".format(c, n))
import bisect
import math
n = int(input())
l = sorted(list(map(int,input().split())))
if len(l)==2 :
  print(l[-1],l[-2])
  exit()
  
a = l[-1]/2
s = bisect.bisect_left(l,a)
if l[s]==a:
  print(l[-1],l[s])
  exit()
k1 = l[s-1]
k2 = l[s]
s1 = a-k1
if k2==l[-1]:
  k2 = k1
#s2 = abs(k2-a)
print(s,k1,k2,s1,s2)
if s1<=s2:
  print(l[-1],k1)
else:
  print(l[-1],k2)

### FIXED CODE ###

import bisect
import math
n = int(input())
l = sorted(list(map(int,input().split())))
if len(l)==2 :
  print(l[-1],l[-2])
  exit()
  
a = l[-1]/2
s = bisect.bisect_left(l,a)
if l[s]==a:
  print(l[-1],l[s])
  exit()
k1 = l[s-1]
k2 = l[s]
s1 = a-k1
if k2==l[-1]:
  k2 = k1
s2 = abs(k2-a)
#print(s,k1,k2,s1,s2)
if s1<=s2:
  print(l[-1],k1)
else:
  print(l[-1],k2)
k = [-1,0,1]
def search(x,y,m):
    if x<0 or x>=len(m[0]) or y<0 or y>=len(m): return
    if m[y][x]==0: return
    m[y][x] = 0
    for i in k:
        for j in k:
            search(x+i,y+j,m)

while True:
    c = 0
    w,h = map(int,input().split())
    if w==0: break
    m = [list(map(int,input().split())) for i in range(h)]
    for i in range(h):
        for j in range(w):
            if m[i][j]==1:
                search(j, i, m)
                c += 1
    print(c)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
def search(x,y,m):
    if not(0<=x<len(m[0]) and 0<=y<len(m)) or m[y][x]=='0': return
    m[y][x] = '0'
    for dx,dy in [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]:
        search(x+dx,y+dy,m)
while True:
    w,h = map(int,input().split())
    if w==h==0: break
    m = [input().split() for _ in range(h)]
    c = 0
    for y in range(h):
        for x in range(w):
            if m[y][x]=='1':
                c += 1
                search(x,y,m)
    print(c)