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

import copy
import collections
import sys


def input():
    return sys.stdin.readline()[:-1]


def bfs(sx, sy, gx, gy):
    # sx,sy := スタートの座標
    # gx,gy := ゴールの座標
    que = collections.deque()
    que.append([sx, sy])
    d = [[inf]*W for _ in range(H)]
    d[sx][sy] = 0
    s = copy.copy(field)
    while (len(que) > 0):
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and s[nx][ny] != "#" and d[nx][ny] == inf):
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]


inf = float('inf')
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
d = [[inf]*W for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

cand = []
memo = []

for h1 in range(H):
    for w1 in range(W):
        if field[h1][w1] == '#':
            continue
        for h2 in range(H):
            for w2 in range(W):
                if field[h2][w2] == '#':
                    continue
                if h1 == h2 and w1 == w2:
                    continue
                cand.append([h1, w1, h2, w2])
for c in cand:
    res = bfs(*c)
    if res != float('inf'):
        memo.append(res)
print(max(memo))


### FIXED CODE ###

import copy
import collections
import sys


def input():
    return sys.stdin.readline()[:-1]


def bfs(sx, sy):
    # sx,sy := スタートの座標
    # gx,gy := ゴールの座標
    que = collections.deque()
    que.append([sx, sy])
    d = [[inf]*W for _ in range(H)]
    d[sx][sy] = 0
    s = copy.copy(field)
    while (len(que) > 0):
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and s[nx][ny] != "#" and d[nx][ny] == inf):
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d  # d[gx][gy]


inf = -1
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
d = [[inf]*W for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

cand = []
memo = []

for h1 in range(H):
    for w1 in range(W):
        if field[h1][w1] == '#':
            continue
        cand.append([h1, w1])
for c in cand:
    res = bfs(*c)
    memo.append(max(sum(res, [])))
print(max(memo))
### BUGGY CODE ###

import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))


def solve():
    n, k =read(); arr = read()
    dp = [float("inf") for i in range(n)]; dp[0] = 0
    for i in range(n):
    	for j in range(1, k+1):
    		if i-j >-1:
    			dp[i] = min(dp[i], dp[i-j]+abs(arr[i-j] - arr[i]))
    # print(dp)
    print(dp[-1])

    

if __name__ == "__main__":
	solve()

### FIXED CODE ###

import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
    n, k =read(); arr = read()
    dp = [-1]*n; dp[0] = 0
    for i in range(n):
    	for j in range(1, k+1):
    		if i-j >-1:
    			tem = dp[i-j]+abs(arr[i-j] - arr[i])
    			if dp[i] == -1:
    				dp[i] = tem
    			elif dp[i] > tem:
    				dp[i] = tem
    				# dp[i] = min(dp[i], tem)
    print(dp[-1])

def one():
	l = [0]*10**7
def two():
	l = [0 for i in range(10**7)]

if __name__ == "__main__":
	solve()
	# cProfile.run(solve())
	# profile.run(one())
	# cProfile.run()
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline


def main():
    sc = Scan()
    n = sc.intarr()[0]
    h = sc.intarr()
    maximum = 0
    for i in range(n):
        count = 0
        before = h[i]
        for j in range(i+1, n):
            if before < h[j]:
                if maximum < count:
                    maximum = count
                break
            count += 1
            before = h[j]
        if maximum < count:
            maximum = count
    print(maximum)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline


def main():
    sc = Scan()
    sc.intarr()[0]
    h = sc.intarr()
    maximum = 0
    count = 0
    before = 0
    for i in h:
        if before < i:
            if maximum < count:
                maximum = count
            count = 0
        else:
            count += 1
        before = i
    if maximum < count:
        maximum = count
    print(maximum)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            
            if j-i != k-j and s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R")*s.count("G")*s.count("B")
for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:
            break
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            ans -= 1

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

S = input()
K = int(input())

A = []
for i in range(len(S)):
    for j in range(1,len(S)+1):
        if S[i:j] != "":
            if len(S[i:j]) < 6:
                A.append(S[i:j])

A = sorted(set(A))
#A = sorted(set(A), key=A.index)
        
print(A[K-1])

### FIXED CODE ###

S = input()
K = int(input())

A = []
for i in range(len(S)):  
    for j in range(1,i + 6):
        if S[i:j] != "":
            A.append(S[i:j])

A = sorted(set(A))
        
print(A[K-1])
### BUGGY CODE ###

N,K = map(int,input().split())
H = 0
while True:
  if (N > K):
    H = N-K
  else:
    H = K - N
  if (H>N):
    break
  else:
    N = H
print(N)
  

### FIXED CODE ###

N,K = map(int,input().split())
H = 0
while True:
  if (N > K):
    H = N%K
  else:
    H = K-N
  if (H>N):
    break
  else:
    N = H
print(N)
### BUGGY CODE ###

N, K, Q = list(map(int, input().split()))

vec = [K for _ in range(N)]

for _ in range(Q):
    A = int(input())
    for i in range(N):
        vec[i] -= 1
    vec[A-1] += 1

ret = '\n'.join(['Yes' if x > 0 else 'No' for x in vec])
print(ret)

### FIXED CODE ###

N, K, Q = list(map(int, input().split()))

# vec = [K for _ in range(N)]

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

for _ in range(Q):
    A = int(input())
#     for i in range(N):
#         vec[i] -= 1
    vec[A-1] += 1

ret = '\n'.join(['Yes' if K-Q+x > 0 else 'No' for x in vec])
print(ret)
### BUGGY CODE ###

H,W = map(int,input().split())
S = []
for i in range(H):
    s = input()
    S.append([x for x in s])

S_t = list(map(list, zip(*S)))

S_h = [[] for i in range(H)]
S_w = [[] for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h[y].append(x)
            S_w[x].append(y)

S_hh = [[0]*(W+1) for i in range(H)]
S_ww = [[0]*(H+1) for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_hh[y][x] = 1
            S_ww[x][y] = 1
        S_hh[y][x] += S_hh[y][x-1]
        S_ww[x][y] += S_ww[x][y-1]

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            c = 1
            if len(S_w[x]) == 0:
                c += H-1
            else:
                i = S_ww[x][y]
                if i == 0:
                    c += S_w[x][0]-1
                elif i == len(S_w[x]):
                    c += H-S_w[x][-1]-2
                else:
                    c += S_w[x][i]-S_w[x][i-1]-2
            if len(S_h[y]) == 0:
                c += W-1
            else:
                i = S_hh[y][x]
                if i == 0:
                    c += S_h[y][0]-1
                elif i == len(S_h[y]):
                    c += W-S_h[y][-1]-2
                else:
                    c += S_h[y][i]-S_h[y][i-1]-2
            ans = max(ans,c)

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input() for i in range(H)]

S_h1 = [[0]*(W+1) for i in range(H)]
S_w1 = [[0]*(H+1) for i in range(W)]
S_h2 = [[0]*(W+1) for i in range(H)]
S_w2 = [[0]*(H+1) for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h1[y][x] = 0
            S_w1[x][y] = 0
        else:
            S_h1[y][x] += S_h1[y][x-1]+1
            S_w1[x][y] += S_w1[x][y-1]+1

for x in range(W-1,-1,-1):
    for y in range(H-1,-1,-1):
        if S[y][x] == '#':
            S_h2[y][x] = 0
            S_w2[x][y] = 0
        else:
            S_h2[y][x] += S_h2[y][x+1]+1
            S_w2[x][y] += S_w2[x][y+1]+1

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            ans = max(ans,S_h1[y][x]+S_h2[y][x]+S_w1[x][y]+S_w2[x][y]-3)
 
print(ans)
### BUGGY CODE ###

from itertools import product
x, y, z, k = map(int, input().split())
A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())
AB = [sum(ab) for ab in product(A, B)]
AB.sort(reverse=True)
AB = AB[:k]
ABC = [sum(abc) for abc in product(AB, C)]
ABC.sort(reverse=True)
for i in range(k):
    print(ABC[i])


### FIXED CODE ###

from itertools import product
x, y, z, k = map(int, input().split())
A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())
AB = [sum(ab) for ab in product(A, B)]
AB.sort(reverse=True)
AB = AB[:k]
ABC = [sum(abc) for abc in product(AB, C)]
ABC.sort(reverse=True)
for i in range(k):
    print(ABC[i])
### BUGGY CODE ###

import math

H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = math.ceil(MAX_A/E_MIN) +1
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(1,(MAX_A+1)):
            KARI = []
            KARI.append(DP[i-1][j])
            if j % Magic[i][0] == 0:
                KARI.append((j//Magic[i][0]) * Magic[i][1])
            r = j // Magic[i][0]
            for k in range(r):
                KARI.append(DP[i-1][j-k*Magic[i][0]]+k*Magic[i][1])
            DP[i][j] = min(KARI)
print(min(DP[N-1][H:MAX_A]))

                
            
        


### FIXED CODE ###

H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]

black = 0
for g in G:
    black += g.count("#")


que = deque()
que.append([0, 0, 0])
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while que:
    nh, nw, cost = que.pop()
    G[nh][nw] = cost
    if G[H - 1][W - 1] != ".":
        print(H * W - black - int(G[H - 1][W - 1]) - 1)
        break

    for dh, dw in direction:
        if (0 <= nh + dh < H) & (0 <= nw + dw < W):
            if G[nh + dh][nw + dw] == ".":
                que.appendleft((nh + dh, nw + dw, cost + 1))
else:
    print(-1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
Field = [list(input()) for i in range(H)]

que = deque()
que.append([0, 0])
Field[0][0] = 0

while que:
    now = que.popleft()
    if now == [H-1, W-1]:
        break

    if now[0]+1 <= H -1:
        if Field[now[0]+1][now[1]] == ".":
            Field[now[0]+1][now[1]] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0]+1, now[1]])

    if now[0]-1 >= 0:
        if Field[now[0]-1][now[1]] == ".":
            Field[now[0]-1][now[1]] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0]-1, now[1]])

    if now[1] + 1 <= W -1:
        if Field[now[0]][now[1]+1] == ".":
            Field[now[0]][now[1]+1] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0], now[1]+1])

    if now[1] -1 >= 0:
        if Field[now[0]][now[1]-1] == ".":
            Field[now[0]][now[1]-1] = str(int(Field[now[0]][now[1]])+1)
            que.append([now[0], now[1]-1])
else:
    print(-1)
    exit()
Z = int(Field[H-1][W-1])

sharp_cnt = 0
for f in Field:
    sharp_cnt += f.count("#")

print(H*W - sharp_cnt - Z - 1)
### BUGGY CODE ###

from fractions import gcd
#from math import gcd
 
def lcm(m, n): return m * n // gcd(m, n)
 
n = int(input())
a = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
mulab = 1
for i in range(n):
    mulab = lcm(mulab, a[i])
 
ans = 0
for i in range(n):
    ans = (ans + mulab // a[i]) % MOD
 
print(ans)

### FIXED CODE ###

from fractions import gcd
#from math import gcd
 
def lcm(m, n): return m * n // gcd(m, n)
 
n = int(input())
a = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
mulab = 1
for i in range(n):
    mulab = lcm(mulab, a[i])
 
mulab %= MOD
ans = 0
for i in range(n):
    #フェルマーの小定理
    ans = ans + mulab * pow(a[i], MOD-2, MOD)
    ans %= MOD
 
print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())

a_list = list(map(int, input().split()))

ans_dict = {}
value_dict = {1: 0}
for i in range(n):
    if i in ans_dict.keys():
        print(ans_dict[i])
    else:
        buff = a_list[:i]
        buff.extend(a_list[i+1:])
        c = Counter(buff)

        tmp_ans = 0
        for value in c.values():
            if value in value_dict.keys():
                tmp_ans += value_dict[value]
            else:
                tmp = (value * (value - 1))/2
                tmp_ans += tmp
                value_dict[value] = tmp
        ans_dict[i] = tmp_ans
        print(int(tmp_ans))




### FIXED CODE ###

from collections import Counter

n = int(input())

a_list = list(map(int, input().split()))

c = Counter(a_list)

all_count = 0
for value in c.values():
    if value == 1:
        continue
    else:
        tmp = int((value * (value - 1))/2)
        all_count += tmp

for i in a_list:
    print(all_count - c[i] + 1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
 
val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,input().split())
    val[a-1] += b 
visited = [True for i in range(N)]
def dps(i):
    visited[i] = False
    if i == N :
        return 1
    else :
        for j in graph[i]:
            if visited[j]:
                val[j] += val[i]
                dps(j)
dps(0)
for i in val:
  print(i,end = " ")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,readline().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,readline().split())
    val[a-1] += b 

def dps(i,parent): 
    for j in graph[i]:
        if j == parent:
            continue
        val[j] += val[i]
        dps(j,i)
                
dps(0,-1)
print(*val)
### BUGGY CODE ###

import copy
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n-1)]
l2=[list(map(int,input().split())) for i in range(q)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[0 for i in range(n)]
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
oya=0
L2=[]
L3=[]
ct=1
while len(L2)!=3*n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
  ct+=1
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))

### FIXED CODE ###

import copy
n,q=map(int,input().split())
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
mod = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
    
for i in range(1,n+1):
    if i in a:
        continue
    x = dp[i-1] 
    if i > 1:
        x += dp[i-2]
    dp[i] = x % mod
ans = dp[n]
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = {int(input()) for _ in range(m)}
mod = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
    
for i in range(1,n+1):
    if i in a:
        continue
    x = dp[i-1] 
    if i > 1:
        x += dp[i-2]
    dp[i] = x % mod
ans = dp[n]
print(ans)
### BUGGY CODE ###

k = int(input())
p = 0

for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
            t = 0
            for i in range(1,min(x,y,z)+1):
                if x % i == 0 and y % i == 0 and z % i == 0:
                    t = i
            p += t

print(p)

### FIXED CODE ###

import math
import itertools

k = int(input())
l = list(range(1,k+1))
y = list(itertools.combinations_with_replacement(l,3))
n = len(y)
t = 0

for i in range(n):
    a = y[i][0]
    b = y[i][1]
    c = y[i][2]
    d = math.gcd(math.gcd(a,b),c)
    if a != b != c:
        t += d * 6
    elif a == b == c:
        t += d
    else:
        t += d * 3

print(t)
### BUGGY CODE ###

#!/usr/bin/env python3
# 基本的には結果は１になるはず。例外は全てKの倍数である時のみ
# minで割って行ってあまりが1ならそれで終了、それ以外は、あまりが異なるものをひいていって、1になったら終了
# あまりのminで更新することができるかどうか
n = int(input())
a = list(map(int,input().split()))
div = min(a)
while True:
    cnt = 0
    for i in range(n):
        if a[i] % div== 0:
            cnt += 1
            a[i] = div
        a[i] = a[i] % div
    if cnt == n: break
print(div)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
def gcd(m,n):
  if m > n: m,n = n,m
  while m != 1:
    if n%m == 0: return m
    m,n = n%m , m
  return m
ans = a[0]
for i in range(n-1):
  ans = gcd(ans,a[i+1])
print(ans)
### BUGGY CODE ###

import time
import math

def main():
    N, M = [int(n) for n in input().split()]
    A = [int(n) for n in input().split()]
    B = [0]*(N+1)
    B[0] = 0
    d = {}
    for i in range(N):
        B[i+1] = B[i] + A[i]
    for i, b in enumerate(B):
        x = b % M
        if x in d.keys():
            d[x] += 1
        else:
            d[x] = 1
    # print(B)
    print(sum([i * (i - 1)//2 for i in d.values()]))
        
c = {}
f = math.factorial
def C(n, r):
    if (n, r) in c.keys():
        return c[n, r]
    if n < 0 or r<0 or n<r:
        return 0
    c[(n, r)] = f(n) // (f(n-r) * f(r))
    return c[(n, r)]


# import os,sys, time

# current = os.path.abspath(__file__ + "/..")+"/"
# fdr = open(current + "d-case1.txt", "r")
# sys.stdin = fdr
# t = time.time()
# main()
# print(time.time() - t)

main()


### FIXED CODE ###


def main():
    N, M = [int(n) for n in input().split()]
    A = [int(n) for n in input().split()]
    B = [0]*(N+1)
    B[0] = 0
    d = {}
    accum = 0
    for i in range(N+1):
        B[i] = accum
        if i != N:
            accum += A[i]
    
    for i, b in enumerate(B):
        x = b % M
        if x in d.keys():
            d[x] += 1
        else:
            d[x] = 1
    # print(B)
    print(sum([i * (i - 1)//2 for i in d.values()]))
        
# import os,sys, time

# current = os.path.abspath(__file__ + "/..")+"/"
# fdr = open(current + "d-case1.txt", "r")
# sys.stdin = fdr
# t = time.time()
# main()
# print(time.time() - t)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,K = map(int, input().split())
H = list(map(int, input().split()))

dp = [0 for _ in range(N+1)]

for i in range(N):
    if i == 0:
        dp[i] = 0
    for k in range(1,min(K,i)+1):
        if k == 1:
            dp[i] = dp[i-k] + abs(H[i]-H[i-k])
        else:
            dp[i] = min(dp[i],dp[i-k] + abs(H[i]-H[i-k]))


print(dp[N-1])


### FIXED CODE ###

N,K = map(int, input().split())
H = list(map(int, input().split()))

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

for i in range(N):
    if i == 0:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + abs(H[i]-H[i-1])
        for k in range(2,min(K,i)+1):
            dp[i] = min(dp[i-k] + abs(H[i]-H[i-k]),dp[i])

print(dp[N-1])
### BUGGY CODE ###

s = input()
n = len(s)
dp = [0 for _ in range(n)]
dp[-1] = int(s[-1])
for i in range(n-2, -1, -1):
    dp[i] = (dp[i+1] + int(s[i]) * (10**(n-i-1))) % 2019

cnt_dic = {}

for i in dp:
    if not i in cnt_dic:
        cnt_dic[i] = 0

    cnt_dic[i] += 1

# print(dp)
ans = 0
# print(cnt_dic)
for i, j in cnt_dic.items():
    if i == 0:
        ans += j
    else:
        ans += j * (j - 1) // 2

print(ans)

### FIXED CODE ###

s = input()
n = len(s)
dp = [0 for _ in range(n)]
dp[-1] = int(s[-1])
memo = 0
cnt_dic = {}
tmp = 1
ans = 0
cnt_dic[0] = 1
for i in range(n-1, -1, -1):
    memo = (memo + int(s[i]) * pow(10, n-i-1, 2019)) % 2019
    if not memo in cnt_dic:
        cnt_dic[memo] = 0
    ans += cnt_dic[memo]
    cnt_dic[memo] += 1

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

N = int(input())
A_list = list(map(int,input().split()))
Q = int(input())
for i in range(Q):
    B,C = map(int,input().split())
    for j in A_list:
        if j == B:
            A_list[A_list.index(j)] = C
    print(sum(A_list))

### FIXED CODE ###

N = int(input())
A_list = list(map(int,input().split()))
Q = int(input())
S = sum(A_list)
count_list = [0] * (10 ** 5 + 1)
for A in A_list:
    count_list[A] += 1 
for i in range(Q):
    B,C = map(int,input().split())
    S = S + count_list[B] * (C - B)
    count_list[C] += count_list[B]
    count_list[B] = 0
    print(S)
#    print(sum(A_list))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def I(): return int(input())


def main():
    K = I()
    result = -1
    num = 1
    if K % 2 == 0 or K %  5 == 0:
        print(-1)
        exit()
    if K % 7 == 0:
        K = 9*K//7
    else:
        K = 9*K
    for i in range(10**6):
        num *= 10
        if num % K == 1:
            print(i+1)
            exit()
    print(-1)
            

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def I(): return int(input())


def main():
    K = I()
    if K % 2 == 0 or K %  5 == 0:
        print(-1)
        exit()
    if K % 7 == 0:
        K = 9*K//7
    else:
        K = 9*K
    amari = 1
    for i in range(10**6):
        amari = amari*10 % K
        if amari == 1:
            print(i+1)
            exit()
    print(-1)

if __name__ == "__main__":
    main()