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

def main():
    import heapq
    inf = 10**8
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start = (start[0]-1, start[1]-1)
    goal = (goal[0]-1, goal[1]-1)
    grid = [input() for _ in [0]*h]
    dist = [[inf]*w for _ in [0]*h]
    q = [(0, start)]
    dist[start[0]][start[1]] = 0
    heapq.heapify(q)
    while q:
        d, (nowx, nowy) = heapq.heappop(q)
        for i, j in [(nowx-1, nowy), (nowx+1, nowy), (nowx, nowy-1), (nowx, nowy+1)]:
            if i < 0 or i >= h or j < 0 or j >= w:
                continue
            if grid[i][j] == "#":
                continue
            if dist[i][j] > d:
                dist[i][j] = d
                heapq.heappush(q, (d, (i, j)))
        for i in range(nowx-2, nowx+3):
            for j in range(nowy-2, nowy+3):
                if i < 0 or i >= h or j < 0 or j >= w:
                    continue
                if grid[i][j] == "#":
                    continue
                if dist[i][j] > d+1:
                    dist[i][j] = d+1
                    heapq.heappush(q, (d+1, (i, j)))
    if dist[goal[0]][goal[1]] == inf:
        print(-1)
        return
    print(dist[goal[0]][goal[1]])


main()


### FIXED CODE ###

def main():
    import heapq
    inf = 10**8
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start = (start[0]-1, start[1]-1)
    goal = (goal[0]-1, goal[1]-1)
    grid = [input() for _ in [0]*h]
    dist = [[inf]*w for _ in [0]*h]
    q = [(0, start)]
    dist[start[0]][start[1]] = 0
    heapq.heapify(q)
    while q:
        d, (nowx, nowy) = heapq.heappop(q)
        for i, j in [(nowx-1, nowy), (nowx+1, nowy), (nowx, nowy-1), (nowx, nowy+1)]:
            if i < 0 or i >= h or j < 0 or j >= w:
                continue
            if grid[i][j] == "#":
                continue
            if dist[i][j] > d:
                dist[i][j] = d
                heapq.heappush(q, (d, (i, j)))
        for i in range(nowx-2, nowx+3):
            for j in range(nowy-2, nowy+3):
                if i < 0 or i >= h or j < 0 or j >= w:
                    continue
                if grid[i][j] == "#":
                    continue
                if dist[i][j] > d+1:
                    dist[i][j] = d+1
                    heapq.heappush(q, (d+1, (i, j)))
    if dist[goal[0]][goal[1]] == inf:
        print(-1)
        return
    print(dist[goal[0]][goal[1]])


main()
### BUGGY CODE ###

import sys
import collections

n = input()
arr = [_.replace('\n', '') for _ in sys.stdin]
dic = collections.Counter(arr)

s = [k for k,v in dic.items() if v == max(dic.values())]
for i in sorted(s):
  print(i)


### FIXED CODE ###

import sys
import collections

n = input()
arr = [_.replace('\n', '') for _ in sys.stdin]
dic = collections.Counter(arr)
cnt = list(dic.values()).count(max(dic.values()))
s = [k for k,v in dic.most_common(cnt)]

for i in sorted(s):
  print(i)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc044/tasks/arc060_a

from itertools import combinations


n, a = map(int, input().split())
x = list(map(int, input().split()))
x.sort()

# print(n, a)
# print(x)
ans = 0
for k in range(1, n + 1):
    for comb in combinations(range(n), k):
        avg = 0
        for c in comb:
            avg += x[c]
        avg /= len(comb)
        if avg == a:
            ans += 1
print(ans)

### FIXED CODE ###

# DP

# https://atcoder.jp/contests/abc044/tasks/arc060_a

from itertools import combinations


n, a = map(int, input().split())
x = list(map(int, input().split()))
X = max(max(x), a)


# dp[j][k][s] (0 <= j <= N, 0 <= k <= N, 0 <= s <= NX)
# dp[j][k][s] = x1,...,xjまでからk枚使って，合計をsにする選び方の総数
# dp[0][0][0] = 1
# j >= 1, s < xjのとき，dp[j][k][s] = dp[j-1][k][s] (xjは使わない)
# j >= 1, k >= 1, s >= xjのとき，dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xj]
# ... 1枚少なく使ってxjを入れる + 使わない
# それ以外 0

dp = [
    [[0 for _ in range(n * X + 1)] for _ in range(n + 2)]
    for _ in range(n + 2)
]

dp[0][0][0] = 1
for i in range(n):
    for j in range(n+1):
        for k in range(n * X + 1):
            if k < x[i]:
                dp[i + 1][j][k] = dp[i][j][k]
            else:
                dp[i + 1][j][k] = dp[i][j][k] + dp[i][j-1][k-x[i]]
ans = 0
for i in range(1, n + 1):
    ans += dp[n][i][i*a]
print(ans)
### BUGGY CODE ###

S = input()
T = input()
lenS = len(S)
lenT = len(T)
dp = [[0]*(lenT+1)for _ in range(lenS+1)]

for i in range(1,lenS+1):
    for j in range(1,lenT+1):
        if S[i-1]==T[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans = ""
m = lenS
n = lenT
while m and n:
    if dp[m][n]==dp[m-1][n]:
        m -= 1
    elif dp[m][n]==dp[m][n-1]:
        n -= 1
    else:
        m -= 1
        n -= 1
        ans = T[n]+ans

print(ans)


### FIXED CODE ###

# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

n,m = map(int,input().split(' '))
cost = 0
count = 0

mlist = list()
for i in range(n):
  mlist.append(list(map(int,input().split(' '))))
  mlist.sort(key=lambda x: x[0])

for i in range(n):
  ablist = mlist[i]
  if count+ablist[1] <= m:
    count += ablist[1]
    cost += ablist[0]*ablist[1] 
  else:
    for j in range(ablist[1]):
      count += 1
      if count <= m:
        cost += ablist[0]
print(cost)


### FIXED CODE ###

n,m = map(int,input().split(' '))
cost = 0
count = 0

mlist = list()
for i in range(n):
  mlist.append(list(map(int,input().split(' '))))
mlist.sort(key=lambda x: x[0])

for i in range(n):
  ablist = mlist[i]
  if count+ablist[1] <= m:
    count += ablist[1]
    cost += ablist[0]*ablist[1] 
  else:
    for j in range(ablist[1]):
      count += 1
      if count <= m:
        cost += ablist[0]
      else:
        break_t = True
        break
    if break_t:
      break
print(cost)
### BUGGY CODE ###

#!/usr/bin/env python3
 
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

import sys
import math
import copy
a = int(input());
b = [int(input()) for i in range(a)];
c = 0;
first = max(b);
g = b.copy();
h = g.index(first);
del g[h];
second = max(g);

for i in range(a):
    if max(b) > b[i]:
        print(first);
    elif first == b[i]:
        print(second);

### FIXED CODE ###

import sys
import math
import copy
a = int(input());
b = [int(input()) for i in range(a)];
c = 0;
first = max(b);
g = b.copy();
h = g.index(first);
del g[h];
second = max(g);

for i in range(a):
    if first > b[i]:
        print(first);
    elif first == b[i]:
        print(second);
### BUGGY CODE ###

N,K = map(int,input().split(" "))
height = []
for i in range(N):
    height.append(int(input()))
height.sort()
min = 10**9
n = N-K+1
for j in range(n):
    light = height[j:j+K]
    hmin = light[0]
    hmax = light[K-1]
    hei = hmax-hmin
    if hei <= min:
        min = hei
print(min)

### FIXED CODE ###

N,K = map(int,input().split(" "))
height = []
for i in range(N):
    height.append(int(input()))
height.sort()
min = 10**9
n = N-K+1
for j in range(n):
    hmin = height[j]
    hmax = height[j+K-1]
    hei = hmax-hmin
    if hei <= min:
        min = hei
print(min)
### BUGGY CODE ###

class UnionFind():
  def __init__(self,n):
    self.parents = [-1]*n
  
  def find(self,x):
    if self.parents[x] < 0:
      return x
    
    self.parents[x] = self.find(self.parents[x])
    return self.parents[x]
  
  def union(self,x,y):
    x = self.find(x)
    y = self.find(y)
    
    if x==y:
      return
    
    if self.parents[x]>self.parents[y]:
      x,y=y,x
      
    self.parents[x] += self.parents[y]
    self.parents[y] = x


import numpy as np
 
N,M=map(int,input().split())
uf = UnionFind(N+1)
 
ans_max=(N)*(N-1)//2
ans=[]
L=[]
 
for i in range(M):
  a,b=map(int,input().split())
  L.append((a,b))

for i in range(M):
  temp=np.array(uf.parents) 
  temp_sum=sum(abs(temp[temp<0])*(abs(temp[temp<0])-1)//2)
  ans.append(temp_sum)
  uf.union(L[M-1-i][0],L[M-1-i][1])


x = lambda ans:ans_max-ans

for i in range(M):
  print(x(ans[M-1-i]))
  


### FIXED CODE ###

class UnionFind():
  def __init__(self,n):
    self.parents = list(range(n))
    self.size = [1]*n
  
  def find(self,x):
    if self.parents[x] == x:
      return x
	
    self.parents[x] = self.find(self.parents[x])
    return self.parents[x]
  
  def union(self,x,y):
    x = self.find(x)
    y = self.find(y)
    
    if x==y:
      return
    
    if self.size[x]<self.size[y]:
      x,y=y,x
	
    self.size[x]+=self.size[y]
    self.parents[y] = x
  
  def same(self,x,y):
    return self.find(x) == self.find(y)
  
  def sizeofset(self,x):
    return self.size[self.find(x)]


N,M=map(int,input().split())
uf = UnionFind(N+1)

cnt=(N)*(N-1)//2
L=[[int(x) for x in input().split()] for _ in range(M)]
ans=[]

for a,b in L[::-1]:
  ans.append(cnt)
  if not uf.same(a,b):
    cnt -= uf.sizeofset(a)*uf.sizeofset(b)
    uf.union(a,b)

for x in ans[::-1]:
  print(x)
### BUGGY CODE ###


from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = defaultdict(set)

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)


### FIXED CODE ###


from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = [set() for _ in range(N+1)]

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)
### BUGGY CODE ###



n = int(input())
s = list(input())

count = 0
for i in range(n):
	for j in range(i + 1, n):
		for k in range(j + 1, n):
			if s[i] != s[j] and s[j] != s[k] and s[i] != s[k] and j != (k + i) / 2:
				count += 1
print(count)


### FIXED CODE ###

from collections import Counter

n = int(input())
s = list(input())
c = Counter(s)
total = c['R'] * c['G'] * c['B']
count = 0
for i in range(n):
	for j in range(i + 1, n):
			k = 2 * j - i
			if k < n and s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
				count += 1
print(total - count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

s = sum(a)
for i in range(int(input())):
    b, c = map(int, input().split())
    for j in range(n):
        if a[j] == b:
            s -= b
            a[j] = c
            s += c
    print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

s = sum(a)
nums = {}
for i in range(n):
    if a[i] in nums:
        nums[a[i]] += 1
    else:
        nums[a[i]] = 1

for i in range(int(input())):
    b, c = map(int, input().split())
    if b in nums:
        s -= nums[b]*b
        s += nums[b]*c
        if c in nums:
            nums[c] += nums[b]
        else:
            nums[c] = nums[b]
        nums[b] = 0
    print(s)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
c=""
for i in range(n):
    c += " " + str(a.index(i+1)+1)
print(c[1:])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l = []
for i in range(n):
    l.append((a[i], i+1)) 
c = sorted(l)
for i in range(n):
    print(c[i][1])
### BUGGY CODE ###

n = int(input())
A = list()
for i in range(n):
    A.append(int(input()))

for i in range(n):
    B = [x for x in A]
    B[i] = 0
    print(max(B))

### FIXED CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
B = A[:]
B.sort(reverse = True)
max_A = max(A)
for i in range(n):
    if A[i] == max_A:
        print(B[1])
    else:
        print(max_A)
### BUGGY CODE ###

l,r=map(int,input().split())
lst=[]
for i in range(l,l+min(4038,r-l+1)):
    lst.append(i%2019)
ans=2018
for i in range(len(lst)-1):
    for j in range(i+1,len(lst)):
        tmp=lst[i]*lst[j]%2019
        if tmp<ans:ans=tmp
print(ans)

### FIXED CODE ###

l,r=map(int,input().split())
if r-l>2019:
    print(0)
    exit()
lst=[]
for i in range(l,l+min(4038,r-l+1)):
    lst.append(i%2019)
ans=2018
for i in range(len(lst)-1):
    for j in range(i+1,len(lst)):
        tmp=lst[i]*lst[j]%2019
        if tmp<ans:ans=tmp
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())

ans = float('inf')

for i in range(n+1):
    ans = min(ans, s[:i].count('#') + s[i+1:].count('.'))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = 0
y = s.count('.')
c = min(n-y, y)
for i in range(n):
    t = s[i] == '#' #＃であればｔがTrueになる
    x += t
    y -= 1 - t
    c = min(c, x+y)
print(c)
### BUGGY CODE ###

X,Y,Z,K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

memo = set([((0,0,0), A[0]+B[0]+C[0]),])

'''
def next(next_cand, (a,b,c)):
  if a<len(A)-1:
    next_cand.append(((a+1,b,c), A[a+1]+B[b]+C[c]))
  if b<len(B)-1:
    next_cand.append(((a,b+1,c), A[a]+B[b+1]+C[c]))
  if c<len(C)-1:
    next_cand.append(((a,b,c+1), A[a]+B[b]+C[c+1]))
'''

while len(memo)<K:
  next_cand=set()
  
  for m in memo:
    #print(m)
    a,b,c = m[0]
    if a<len(A)-1:
      next_cand.add(((a+1,b,c), A[a+1]+B[b]+C[c]))
    if b<len(B)-1:
      next_cand.add(((a,b+1,c), A[a]+B[b+1]+C[c]))
    if c<len(C)-1:
      next_cand.add(((a,b,c+1), A[a]+B[b]+C[c+1]))
      
  #print(next_cand)
  x = list(next_cand - (next_cand&memo))
  #print(x)
           
  x.sort(reverse=True, key=lambda x:x[1])
  #print(x)
  memo.add((x[0]))

memo=sorted(list(memo),reverse=True, key=lambda x:x[1])
for m in memo:
  a,b,c = m[0]
  print(A[a] +B[b] +C[c])



### FIXED CODE ###

X,Y,Z,K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

import heapq

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
m = A[0]+B[0]+C[0]

counted=set([])
in_heap=set([])

hp = []
heapq.heapify(hp)
heapq.heappush(hp, (0, (0,0,0)))

#print(hp)

for _ in range(K):
  x = heapq.heappop(hp)
  print(m-x[0])
  counted.add(x[1])
  a,b,c = x[1]
  if (a+1, b,c) not in counted and (a+1, b,c) not in in_heap and a<len(A)-1:
    heapq.heappush(hp, (m-A[a+1]-B[b]-C[c], (a+1,b,c)))
    in_heap.add((a+1, b, c))
  if (a, b+1,c) not in counted and (a, b+1,c) not in in_heap and b<len(B)-1:
    heapq.heappush(hp, (m-A[a]-B[b+1]-C[c], (a,b+1,c)))
    in_heap.add((a,b+1,c))
  if (a, b,c+1) not in counted and (a, b,c+1) not in in_heap and c<len(C)-1:
    heapq.heappush(hp, (m-A[a]-B[b]-C[c+1], (a,b,c+1)))
    in_heap.add((a,b,c+1))
### BUGGY CODE ###

import math
N, K = map(int, input().split())

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while N > math.ceil(K / 2):
                N = abs(N-K)
        print(N)

### FIXED CODE ###

import math
N, K = map(int, input().split())

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while N >= math.ceil(K / 2):
                N = abs(N-K*(N//K+1))
        print(N)
### BUGGY CODE ###

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

num = 0
blue = 0
red = 0
for i in range(10**18):
    if i % 2 == 0 and N >= num:
        num += A
        blue += 1
    elif i % 2 == 1 and N >= num:
        num += B
        red += 1

    else:
        break
# print(num)
# print(blue)
# print(red)

if blue > red:
    aa = N - A * blue - B * red
    ans_b = A * blue + aa
else:
    aa = N - A * blue - B * red
    ans = B * red + aa
    ans_b = N - ans

print(ans_b)

### FIXED CODE ###

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

A_amari = A % 2
B_amari = B % 2

# print(A_amari)
# print(B_amari)

if A+B == 0:
    print(0)
    exit()
else:
    cnt = N // (A+B)
    amari = N % (A+B)

# print(cnt)
# print(amari)
if amari <= A:
    print(A*cnt+amari)
else:
    if amari <= B or amari > A:
        print(A*(cnt+1))
### BUGGY CODE ###

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,max):
        fac[i] = fac[i-1]*i%mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod

def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k]*finv[n-k]%mod)%mod

mod = 10**9+7

K = int(input())
S = input()
N = len(S)
max = N+K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
modlist1 = []
modlist2 = []
a = 1
b = 1
for i in range(K+1):
    modlist1.append(a)
    modlist2.append(b)
    a = a*26%mod
    b = b*25%mod

ans = 0
for i in range(K+1):
    x = COM(N+K-i-1,N-1)
    y = modlist1[i]
    z = modlist2[K-i]
    xyz = ((x*y%mod)*z)%mod
    ans = (ans+xyz)%mod
print(ans)


### FIXED CODE ###

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,max):
        fac[i] = fac[i-1]*i%mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod

def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k]*finv[n-k]%mod)%mod

mod = 10**9+7

K = int(input())
S = input()
N = len(S)
max = N+K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
modlist1 = []
modlist2 = []
a = 1
b = 1
for i in range(K+1):
    modlist1.append(a)
    modlist2.append(b)
    a = a*26%mod
    b = b*25%mod

ans = 0
for i in range(K+1):
    x = COM(N+K-i-1,N-1)
    y = modlist1[i]
    z = modlist2[K-i]
    xyz = ((x*y%mod)*z)%mod
    ans = (ans+xyz)%mod
print(ans)
### BUGGY CODE ###

#前計算
#素数のリスト作成
N = 10 ** 5 + 10
def primes(n):
    import math
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 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]]

prime_lst = primes(N)
# print (prime_lst, len(prime_lst))
count_lst = [0] * (N + 1)

def check(n):
    if n%2 == 0:
        return False
    if not n  in prime_lst:
        return False
    if not ((n + 1)//2) in prime_lst:
        return False
    return True


for i in range(3, N + 1):
    if check(i):
        count_lst[i] = count_lst[i - 1] + 1
    else:
        count_lst[i] = count_lst[i - 1]

# print (count_lst)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print (count_lst[r] - count_lst[l - 1])

### FIXED CODE ###

#前計算
#素数のリスト作成
N = 10 ** 5 + 10
def primes(n):
    import math
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 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]]

prime_lst = primes(N)
# print (prime_lst, len(prime_lst))
count_lst = [0] * (N + 1)

def check(n):
    if n%2 == 0:
        return False
    if not n  in prime_lst:
        return False
    if not ((n + 1)//2) in prime_lst:
        return False
    return True


for i in range(3, N + 1):
    if check(i):
        count_lst[i] = count_lst[i - 1] + 1
    else:
        count_lst[i] = count_lst[i - 1]

# print (count_lst)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print (count_lst[r] - count_lst[l - 1])
### BUGGY CODE ###

def solve(K):
    checked = [0] * (K + 1)
    queue = [(1, 1)]
    checked[1] = 1
    while queue:
        x, n = queue.pop(0)
        # print((x, n), queue)
        if x == 0:
            return n
        _ = (x * 10) % K 
        if checked[_] == 0 or n < checked[_]:
            queue.insert(0, (_, n))
            checked[_] = n
        _ = (x + 1) % K 
        if checked[_] == 0 or n + 1 < checked[_]:
            queue.append((_, n + 1))
            checked[_] = n + 1
    return None

K = int(input())
print(solve(K))



### FIXED CODE ###

from collections import deque

def solve(K):
    checked = [99999999999] * (K + 1)
    queue = deque()
    queue.append((1, 1))
    checked[1] = 1
    while queue:
        x, n = queue.popleft()
        if x == 0:
            return n
        _ = (x * 10) % K 
        if n < checked[_]:
            queue.appendleft((_, n))
            checked[_] = n
        _ = (x + 1) % K 
        if n + 1 < checked[_]:
            queue.append((_, n + 1))
            checked[_] = n + 1
    return None

K = int(input())
print(solve(K))