Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from heapq import *
INF = 1e10

def floyd(n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

N,M,L = map(int,input().split())

d = [[INF]*N for i in range(N)]

for x in range(M):
    a,b,w = map(int,input().split())
    d[a-1][b-1] = w
    d[b-1][a-1] = w
    d[a-1][a-1] = 0
    d[b-1][b-1] = 0

floyd(N)
grafo2 = [[INF] * N for i in range(N)]

for x in range(len(d)):
    for y in range(len(d[x])) :
        if d[x][y] <= L:
            grafo2[x][y] = 1
            grafo2[y][x] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            grafo2[i][j] = min(grafo2[i][j], grafo2[i][k] + grafo2[k][j])

query = int(input())

for x in range(query):
    s,t = map(int,input().split())
    if grafo2[s-1][t-1] == INF:
        print(-1)
    else:
        print(grafo2[s-1][t-1] - 1)


### FIXED CODE ###

from heapq import *
INF = 1e10

def floyd(n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

N,M,L = map(int,input().split())

d = [[INF]*N for i in range(N)]

for x in range(M):
    a,b,w = map(int,input().split())
    d[a-1][b-1] = w
    d[b-1][a-1] = w

floyd(N)

grafo2 = [[INF] * N for i in range(N)]

for x in range(N):
    for y in range(N) :
        if d[x][y] <= L:
            grafo2[x][y] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if grafo2[i][j] > grafo2[i][k] + grafo2[k][j]:
                grafo2[i][j] = grafo2[i][k] + grafo2[k][j]

query = int(input())

for x in range(query):
    s,t = map(int,input().split())
    if grafo2[s-1][t-1] == INF:
        print(-1)
    else:
        print(grafo2[s-1][t-1] - 1)
### BUGGY CODE ###

# ABC066-C
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    b.append(a[i])
    b = list(reversed(b))
print(' '.join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
start = n // 2 
if n % 2 == 0:
    for i in range(n-1, 0, -2):
        b.append(a[i])
    for i in range(0, n, +2):
        b.append(a[i])
else:
    for i in range(n-1, -1, -2):
        b.append(a[i])
    for i in range(1, n, +2):
        b.append(a[i])

print(" ".join(map(str, b)))
### BUGGY CODE ###

import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    def isPrime(n):
        if n == 2:
            return True
        if n%2 == 0 or n == 1:
            return False
        m = math.floor(math.sqrt(n))+1
        for p in range(3,m,2):
            if n%p == 0:
                return False
        return True

    q = int(input())
    list = []
    for i in range(q):
        cnt = 0
        l,r = map(int, input().split())
        for k in range(l,r+1):
            if k != 2 and k%2==0:
                pass
            else:
                if isPrime(k) and isPrime((k+1)//2):
                    cnt += 1
        list.append(cnt)
    print("\n".join(map(str, list)))

if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

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

    q = int(input())
    primes_num, is_primes = primes(10**5+5)
    sums = []
    cnt = 0

    for i in range(0, 10**5+4):
        if i%2!=0:
            a = (i+1)//2
            if is_primes[i] and is_primes[a]:
                cnt += 1
        sums.append(cnt)

    for i in range(q):
        l,r = map(int, input().split())
        print(sums[r] - sums[l-1])

if __name__=="__main__":
    main()
### BUGGY CODE ###

from sys import stdin
rr = lambda: stdin.readline().strip()

N = int(rr())
A = map(int, rr().split())
MOD = 10**9 + 7
ct, ans = 0, 1
for x in A:
    ct += 1
    while ct > (x + 1)/2:
        ans *= ct
        ans %= MOD
        ct -= 1
while ct:
    ans *= ct
    ans %= MOD
print ans


### FIXED CODE ###

from sys import stdin
rr = lambda: stdin.readline().strip()

N = int(rr())
A = map(int, rr().split())
MOD = 10**9 + 7
ct, ans = 0, 1
for x in A:
    ct += 1
    while ct > (x + 1)/2:
        ans *= ct
        ans %= MOD
        ct -= 1
for k in xrange(1, ct+1):
    ans *= k
    ans %= MOD
print ans
### BUGGY CODE ###

N,M = map(int,input().split())
L = []
for _ in range(M):
    a,b = map(int,input().split())
    L.append([a,b])
L = sorted(L,key = lambda x:x[1])
cnt = 0
while len(L):
    now = L.pop(0)
    cnt += 1
    while len(L):
        if L[0][0] + 1 <= now[1]  and now[1]  < L[0][1] + 1:
            L.pop(0)
        else:
            break
print(cnt)





### FIXED CODE ###

N,M = map(int,input().split())
L = []
for _ in range(M):
    a,b = map(int,input().split())
    L.append([a,b])
L = sorted(L,key = lambda x:x[1])
cnt = 0
while len(L):
    now = L.pop(0)
    cnt += 1
    while len(L):
        if L[0][0] <= now[1] - 0.5 and now[1] - 0.5  <= L[0][1]:
            L.pop(0)
        else:
            break
print(cnt)
### BUGGY CODE ###

H, W = list(map(int, input().split()))
M = [[True for w in range(W)] for h in range(H)]
for h in range(0, H):
    Col = list(input())
    for w in range(0, W):
        if Col[w] == '#':
            M[h][w] = False
mx = 0
for h in range(0, H):
    for w in range(0, W):
        if not M[h][w]:
            continue
        c = 1
        for d in range(w - 1, -1, -1):
            if not M[h][d]:
                break
            c += 1
        for d in range(w + 1, W):
            if not M[h][d]:
                break
            c += 1
        for d in range(h - 1, -1, -1):
            if not M[d][w]:
                break
            c += 1
        for d in range(h + 1, H):
            if not M[d][w]:
                break
            c += 1
        if c > mx:
            mx = c
print(mx)

### FIXED CODE ###

H, W = list(map(int, input().split()))
M = [['.' for w in range(W)] for h in range(H)]
for h in range(0, H):
    M[h] = list(input())

Yoko = [[0 for w in range(W)] for h in range(H)]
Tate = [[0 for w in range(W)] for h in range(H)]
for h in range(0, H):
    for w in range(0, W):
        if M[h][w] != '#':
            if w > 0 and M[h][w - 1] != '#':
                Yoko[h][w] = Yoko[h][w - 1]
            else:
                c = 0
                for d in range(w, W):
                    if M[h][d] == '#':
                        break
                    c += 1
                Yoko[h][w] = c
for w in range(0, W):
    for h in range(0, H):
        if M[h][w] != '#':
            if h > 0 and Tate[h - 1][w] > 0:
                Tate[h][w] = Tate[h - 1][w]
            else:
                c = 0
                for d in range(h, H):
                    if M[d][w] == '#':
                        break
                    c += 1
                Tate[h][w] = c
mx = 0
for w in range(0, W):
    for h in range(0, H):
        c = Yoko[h][w] + Tate[h][w] - 1
        if c > mx:
            mx = c
print(mx)
### BUGGY CODE ###

import bisect
A, B, Q = map(int, input().split())
S = [-10**11] + [int(input()) for i in range(A)] + [10**11]
T = [-10**11] + [int(input()) for i in range(B)] + [10**11]

for _ in range(Q):
    x = int(input())
    a = bisect.bisect_left(S, x)
    b = bisect.bisect_left(T, x)
    print(min(x - min(S[a-1], T[b-1]), max(S[a], T[b]) - x, x+T[b]-2*S[a-1], x+S[a]-2*T[b-1], 2*T[b]-x-S[a-1], 2*S[a]-x-T[b-1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
A, B, Q = map(int, input().split())
S = [-10**11] + [int(input()) for i in range(A)] + [10**11]
T = [-10**11] + [int(input()) for i in range(B)] + [10**11]

for _ in range(Q):
    x = int(input())
    a = bisect.bisect_left(S, x)
    b = bisect.bisect_left(T, x)
    print(min(x - min(S[a-1], T[b-1]), max(S[a], T[b]) - x, x+T[b]-2*S[a-1], x+S[a]-2*T[b-1], 2*T[b]-x-S[a-1], 2*S[a]-x-T[b-1]))
### BUGGY CODE ###

S = input()
N = len(S)
count = 0
for i in range(5,N):
    for j in range(0,N-i+1):
        if int(S[j:j+i])%2019 == 0:
            count += 1
print(count)

### FIXED CODE ###

#数字列の逆順をSにいれる
S = input()[::-1]
#各modの値を数えるためのリスト
counts = [0]*2019
#mod==0になったら1つだけでも2019の倍数になっているので初めから＋１しておく
counts[0] = 1
#numはSの各桁の数字、dは桁数（1の位、10の位、、）
num,d = 0,1
for i in S:
    num += int(i)*d
    num %= 2019
    d *= 10
    #ここがポイント。かける桁数の値も先にmodを計算してからかけると計算量が減らせる。
    d %= 2019
    counts[num] += 1

ans = 0
for i in counts:
    ans += i*(i-1)//2

print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
for ki in k:
    ans = 0
    DMC = [0]*3
    for i, c in enumerate(s):
        if c == "D":
            DMC[0] += 1
        elif c == "M":
            DMC[1] += 1
            DMC[2] += DMC[0]
        if i >= ki:
            j = i-ki
            if s[j] == "D":
                DMC[0] -= 1
                DMC[2] -= DMC[1]
            elif s[j] == "M":
                DMC[1] -= 1
        if c == "C":
            ans += DMC[2]
    print(ans)

### FIXED CODE ###

# コピペ https://atcoder.jp/contests/dwacon5th-prelims/submissions/7670569
# 自分の https://atcoder.jp/contests/dwacon5th-prelims/submissions/7822126
# とほぼ変わらないのに自分のものはTLEするので検証
n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""
 
""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""
 
"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""
 
"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""
 
# 最大公約数 と 最小公倍数
"""def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def lcm(a,b):
  g = gcd(a,b)
  return (a * b) // g"""
 
# 二分探索
"""import bisect # 二分探索
print(A,bisect.bisect_left(A,4))
print(C,n - bisect.bisect_right(C,4))
print(sum(bisect.bisect_left(A,b) * (n-bisect.bisect_right(C,b)) for b in B))"""
 
# 円周率 pi
"""import math
pi_ = math.pi"""
 
# エラトステネスの篩
"""def Erato(n):
    prime = []
    is_prime = [True] * (n+1)
    p = 0
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,n+1):
      if is_prime[i] == True:
        prime.append(i)
        p += 1
        for j in range(2 * i,n+1,i):
          is_prime[j] = False
    return p"""
 
def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def main():
  import fractions
  k = int(input())
  ans = 0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        ans += fractions.gcd(a,fractions.gcd(b,c))
  print(ans)
if __name__ == '__main__':
  main()

### FIXED CODE ###

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def main():
  k = int(input())
  ans = 0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        ans += gcd(a,gcd(b,c))
  print(ans)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import numpy as np

def receive_shopping_plan():
    num_commodity, num_coupon = input().split(' ')
    num_commodity, num_coupon = int(num_commodity), int(num_coupon)
    return num_commodity, num_coupon

def calc_minimized_sum(num_commodity, num_coupon):
    princes = np.array(input().split(' '), dtype='i')
    for _ in range(num_coupon):
        princes[princes.argmax()] //= 2
        if princes.max() <= 0:
            break
    print(princes.sum())

if __name__ == '__main__':
    num_commodity, num_coupon = receive_shopping_plan()
    calc_minimized_sum(num_commodity, num_coupon)


### FIXED CODE ###

import heapq

def receive_shopping_plan():
    num_commodity, num_coupon = input().split(' ')
    num_commodity, num_coupon = int(num_commodity), int(num_coupon)
    return num_commodity, num_coupon

def calc_minimized_sum(num_commodity, num_coupon):
    prices = list(map(lambda x: int(x) * -1 , input().split(' ')))
    heapq.heapify(prices)
    for _ in range(num_coupon):
        max_price = heapq.heappop(prices) // (2*-1)
        heapq.heappush(prices, max_price*-1)

    print(sum(prices)*-1)

if __name__ == '__main__':
    num_commodity, num_coupon = receive_shopping_plan()
    calc_minimized_sum(num_commodity, num_coupon)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
S = input()

# 集合を使う
shugo = set()

keta = [i for i in range(N)]
r = N - 3

ncr = list(combinations(keta, r))

for i in ncr:
    s = ""
    for j in range(len(S)):
        if j in i:
            pass
        else:
            s += S[j]
    shugo.add(s)

print(len(shugo))

### FIXED CODE ###

N = int(input())
S = input()
flag = False
ans = 0
for i in range(1000):
    p = str(i).zfill(3)
    a = [-1, -1, -1]
    for j in range(len(S)):
        if p[0] == S[j]:
            a[0] = j
            break
    if a[0] != -1:
        for k in range(a[0] + 1, len(S)):
            if p[1] == S[k]:
                a[1] = k
                break
    else:
        continue
    if a[1] != -1:
        for l in range(a[1] + 1, len(S)):
            if p[2] == S[l]:
                a[2] = l
                break
    else:
        continue
    if a[2] != -1:
        ans += 1

print(ans)
### BUGGY CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]


count = [0 for i in range(max_end)]
tv_times = []
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    for i in range(len(remove_list)):
        time.remove(remove_list[i])
        time.remove(remove_list[i])

    for i in range(len(time)//2):
        # print(time,remove_list)
        for j in range(max(time[2*i]-1,0),time[2*i+1]):
            count[j] += 1

print(max(count))


### FIXED CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(1,len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    time = list(set(time)-set(remove_list))
    time.sort()
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1
ans = -1
for i in range(1,max_end+1):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

print(ans)
### BUGGY CODE ###

n = int(input())

power = 1

p = 1000000000 + 7

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

print(power % p)


### FIXED CODE ###

n = int(input())

power = 1

p = 1000000000 + 7

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

print(power)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
a = [0]
reva = [[] for _ in range(N + 1)]
for _ in range(N - 1): a.append(int(input()))
for i in range(N):
  if a[i] == 0: continue
  reva[a[i]].append(i + 1)
dp = [-1] * (N + 1)
def dfs(x):
  global dp
  if len(reva[x]) == 0:
    dp[x] = 1
    return 1
  t = []
  for y in reva[x]:
    t.append(dfs(y))
  t.sort(reverse = True)
  for i in range(len(t)):
    t[i] += i + 1
  dp[x] = max(t)
  return dp[x]
print(dfs(1) - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
a = [0]
reva = [[] for _ in range(N + 1)]
for _ in range(N - 1): a.append(int(input()))
for i in range(N):
  if a[i] == 0: continue
  reva[a[i]].append(i + 1)
dp = [-1] * (N + 1)
def dfs(x):
  global dp
  if len(reva[x]) == 0:
    dp[x] = 1
    return 1
  t = []
  for y in reva[x]:
    t.append(dfs(y))
  t.sort(reverse = True)
  for i in range(len(t)):
    t[i] += i + 1
  dp[x] = max(t)
  return dp[x]
print(dfs(1) - 1)
### BUGGY CODE ###

def main():
    n,k=map(int,input().split())
    A=tuple(map(int,input().split()))
    L=set(A)
    m=len(L)-k
    if m<=0:
        print(0)
    else:
        D=[A.count(l) for l in L]
        D.sort()
        print(sum(D[:m]))
main()

### FIXED CODE ###

from collections import Counter
def main():
    n,k=map(int,input().split())
    A=Counter(list(map(int,input().split())))
    # Aの重複元の個数を降順に並べてk番以降の和を数える.
    print(sum(sorted(A.values())[::-1][k:]))
main()
### BUGGY CODE ###

N=int(input())
a=input().split()
c=[n for n in range(N)]
print(" ".join([str(a.index(str(_+1))+1) for _ in c]))


### FIXED CODE ###

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

d=[0 for n in range(N)]
for n in range(N):
    d[A[n]-1] = str(n+1)

print(" ".join(d))
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()


def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


cnt = 0
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        t = L[i] + L[j]
        idx = bisect_left(L, t, lo=j + 1)
        cnt += max(0, idx - j - 1)
print(cnt)


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
 
from bisect import bisect_left 
cnt = 0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    t = L[i]+L[j]
    idx = bisect_left(L,t,j+1)
    cnt += max(0,idx-j-1)
print(cnt)
### BUGGY CODE ###

import networkx as nx

N = int(input())

UVW = [list(map(int, input().split())) for _ in range(N - 1)]

G = nx.Graph()

color = [0 for _ in range(N)]  # 0: tbd，1: white, 2: black

for u, v, w in UVW:
    G.add_edge(u - 1, v - 1, weight=w)

color[0] = -1

for i in range(N - 1):
    if color[i] == 0 or i == 0:
        for j in range(i + 1, N):
            if color[j] == 0:
                d = nx.shortest_path_length(G, source=i, target=j, weight="weight")
                if int(d + 0.5) % 2 == 0:
                    color[j] = color[i]
                else:
                    color[j] = color[i] * -1

ans = [1 if i == -1 else 0 for i in color]
print(*ans)


### FIXED CODE ###

import networkx as nx

N = int(input())
UVW = [list(map(int, input().split())) for _ in range(N - 1)]

G = nx.Graph()

color = [0 for _ in range(N)]

for u, v, w in UVW:
    G.add_edge(u - 1, v - 1, weight=w)

color[0] = -1

pred, dist = nx.dijkstra_predecessor_and_distance(G, 0)

c = [dist[i] for i in range(N)]
ans = [1 if i % 2 == 0 else 0 for i in c]
print(*ans)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
A.sort()

def gcd(n,m):
	if m > n:
		n,m = m,n
	a,b = n,m
	while b > 0:
		a,b = b, a%b
	return a

isPC = True

p,s = A[0], A[0]

for n in A[1:]:
	if isPC and gcd(p, n) == 1:
		p *= n
	else:
		isPC = False

	if s > 1:
		s = gcd(s, n)

if isPC:
	print("pairwise coprime")
elif s == 1:
	print("setwise coprime")
else:
	print("not coprime")

### FIXED CODE ###


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
A.sort()

def gcd(n,m):
	if m > n:
		n,m = m,n
	a,b = n,m
	while b > 0:
		a,b = b, a%b
	return a

def isPrime(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	i = 3
	while i * i <= n:
		if n % i == 0:
			return False
		i += 2
	return True

P = [n for n in range(10**3 + 1) if isPrime(n)]
used = [False for _ in range(10**6 + 1)]

isPC = True
s = A[0]

n = A[0]
for p in P:
	if p > n:
		break
	while n % p == 0:
		used[p] = True
		n = n // p
if n > 1:
	used[n] = True

for n in A[1:]:
	if isPC:
		a = n
		for p in P:
			if p > a:
				break
			if a % p == 0 and used[p]:
				isPC = False
				break
			while a % p == 0:
				a = a // p
		if a > 1 and used[a]:
			isPC = False
		else:
			used[a] = True

	if s > 1:
		s = gcd(s, n)

if isPC:
	print("pairwise coprime")
elif s == 1:
	print("setwise coprime")
else:
	print("not coprime")
### BUGGY CODE ###

ans = {}

roop = input()
for k in range(roop):
    str1 = raw_input()
    str2 = raw_input()
    for i in range (-1, len(str1)):
        for j in range(-1, len(str2)):
            if(i == -1 or j == -1):
                ans[i, j] = 0
            else:   
                if(str1[i] == str2[j]):
                    ans[i, j] = ans[i - 1, j - 1] + 1
                else:
                    ans[i, j] = max(ans[i - 1, j], ans[i, j - 1])
    print ans[len(str1) - 1, len(str2) - 1]

### FIXED CODE ###

def LCS():
    str1 = raw_input()
    str2 = raw_input()
    
    after = [0] * (len(str2) + 1)
    
    for i in xrange(1, len(str1) + 1):
        before = after + []
        for j in xrange(1, len(str2) + 1):
             if str1[i - 1] == str2[j - 1]:
                 after[j] = before[j - 1] + 1
             elif after[j - 1] > before[j]: #this is equal to 'max(after[j - 1], before[j])'
                 after[j] = after[j - 1]
    return after[j]

n = input()
for k in xrange(n):
    print LCS()
### BUGGY CODE ###

n = int(input())

l = []

for i in range(1, n // 2 + 1):
    if n % i == 0:
        l.append((i - 1) + (n // i - 1))

print(min(l))


### FIXED CODE ###

import math

n = int(input())

l = []

for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
        l.append((i - 1) + (n // i - 1))

print(min(l))
### BUGGY CODE ###


n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(n - k + 1):
    calc = 0
    for j in range(i, i + k):
        calc += (1 + p[j]) / 2
    
    ans = max(ans, calc)

print(ans)

### FIXED CODE ###


n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(k):
    ans += (p[i] + 1) / 2
calc = ans
for i in range(1, n - k + 1):
    calc += ((p[i + k - 1] + 1) - (p[i - 1] + 1)) / 2
    ans = max(ans, calc)
print(ans)
### BUGGY CODE ###

N, K = [int(n) for n in input().split()]

def cmp(a, b):
    if a > b:
        return a%b
    return abs(a-b)

while True:
    ans = cmp(N, K)
    if 0 <= ans <=2:
        break
    N = ans
print(ans)         


### FIXED CODE ###

N, K = [int(n) for n in input().split()]
print(min(N%K, K-(N%K)))