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

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

L.sort()
cnt = 0
for i in range(N-1):
    for j in range(i):
        a, b = L[i], L[j] 
        k = i + 1
        while L[k] < a + b:
            if a - b < L[k]:
                cnt += 1
            k += 1
            if k >= N:
                break
            
print(cnt)            

### FIXED CODE ###

from bisect import bisect, bisect_left
N = int(input())
L = list(map(int, input().split()))

L.sort()
cnt = 0
for i in range(N-1):
    for j in range(i):
        a, b = L[i], L[j] 
        r = bisect_left(L[i+1:], a+b) + i+1
        cnt += max(r - i - 1, 0)
            
print(cnt)
### BUGGY CODE ###

def solve():
    N = int(input())
    Ss = input()

    strAs = [set() for _ in range(N)]
    for L in range(N-1):
        maxLen = (N-L)//2
        for R in range(L, L+maxLen):
            ss = Ss[L:R+1]
            strAs[R].add(ss)
    strBs = [set() for _ in range(N)]
    for R in reversed(range(1, N)):
        maxLen = (R+1)//2
        for L in range(R-maxLen+1, R+1):
            ss = Ss[L:R+1]
            strBs[L].add(ss)

    ans = 0
    strCands = set()
    for iEn in range(N-1):
        for strA in strAs[iEn]:
            strCands.add(strA)
        for strB in strBs[iEn+1]:
            if strB in strCands:
                lenB = len(strB)
                if lenB > ans:
                    ans = lenB

    print(ans)

solve()


### FIXED CODE ###

N = int(input())
Ss = input()

def isOK(k):
    strAs = ['' for _ in range(N)]
    strBs = ['' for _ in range(N)]
    for L in range(N-k+1):
        R = L+k-1
        ss = Ss[L:R+1]
        strAs[R] = ss
        strBs[L] = ss

    strCands = set()
    for iEn in range(N-1):
        if strAs[iEn] != '':
            strCands.add(strAs[iEn])
        if strBs[iEn+1] != '' and strBs[iEn+1] in strCands:
            return True

    return False


ng, ok = N//2 + 1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

from collections import Counter
import math

def cmb(n, r):
    num = 1
    for i in range(1, r + 1):
        num = num * (n - i + 1) // i
    return num

n = int(input())
a = list(map(int, input().split()))
nn = len(a) - 1
ctr = Counter(a)

f = {}

for aa in a:
    x = 0
    for k, v in ctr.items():
        if k == aa:
            v -= 1
        if v >= 2:
            #c = f[v] // (2 * f[v - 2])
            x += cmb(v, 2)
    print(x)


### FIXED CODE ###

from collections import Counter
import math

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

ctr = Counter(aa)

cmb2 = [0] * 200001
for n in range(2, 200001):
    r = 2
    num = 1
    for i in range(1, r + 1):
        num = num * (n - i + 1) // i
    cmb2[n] = num

x = 0
for k, v in ctr.items():
    x += cmb2[v]

for a in aa:
    k = ctr[a] - 1
    print(x - k)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
d = [set() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].add(b)
    d[b].add(a)

queue=deque([1])
vs = set([1])
vs_bfs = list()
parents = [0] * (N+1)
while queue:
    v = queue.popleft()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        queue.append(u)

dp = [0]*(N+1)
for v in vs_bfs[::-1]:
    r = 1
    for u in d[v]:
        r *= dp[u]+1
    dp[v] = r

dp2 = [0]*(N+1)
for v in vs_bfs:
    if v == 1:
        dp2[v] = dp[v]
        continue
    p = parents[v]
    dp2[v] = dp[v] * ((dp2[p]//(dp[v]+1)) + 1)
for i in range(1, N+1):
    dp2[i] = str(dp2[i] % M)
print("\n".join(dp2[1:]))


### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
d = [list() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

queue=deque([1])
vs = set([1])
vs_bfs = list()
parents = [0] * (N+1)
while queue:
    v = queue.popleft()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        queue.append(u)

dp = [0 for _ in range(N+1)]
dpl = [1 for _ in range(N+1)]
dpr = [1 for _ in range(N+1)]
for v in vs_bfs[::-1]:
    t = 1
    for u in d[v]:
        if u == parents[v]:
            continue
        dpl[u] = t
        t = (t * (dp[u]+1)) % M
    t = 1
    for u in d[v][::-1]:
        if u == parents[v]:
            continue
        dpr[u] = t
        t = (t * (dp[u]+1)) % M
    dp[v] = t

dp2 = [0]*(N+1)
for v in vs_bfs:
    if v == 1:
        dp2[v] = 1
        continue
    p = parents[v]
    dp2[v] = (dp2[p] * (dpl[v]*dpr[v]) +1)% M
#    print(dp2[p] * (dpl[v]*dpr[v]))
#    dp2[v] = dp2[p] %M
r = [0]*N
for i in range(1, N+1):
    r[i-1] = str(dp[i] * dp2[i] % M)
print("\n".join(r))
### BUGGY CODE ###

n = int(input()) #長さ
s = str(input()) #文字列
cnt = 0 #暗証番号数
 
for a in range(10): #1文字目
  for b in range(10): #2文字目
    for c in range(10): #3文字目
        flg = False
        for i in range(n-2):
            if str(a) == s[i]:
                tmp_i = i + 1
                for j in range(tmp_i,n-1):
                    if str(b) == s[j]:
                        tmp_i = j + 1
                        for k in range(tmp_i,n):
                            if str(c) == s[k]:
                                cnt = cnt + 1
                                flg = True
                                break
                        if flg:
                            break
                if flg:
                    break
            
print(cnt)

### FIXED CODE ###

n = int(input()) #長さ
s = str(input()) #文字列
cnt = 0 #暗証番号数

for a in range(10): #1文字目
  for b in range(10): #2文字目
    for c in range(10): #3文字目
      flg = False
      check_a = s.find(str(a))
      if check_a != -1:
        tmp_s = s[check_a + 1:]
        check_b = tmp_s.find(str(b))
        if check_b != -1:
          tmp_t = tmp_s[check_b + 1:]
          check_c = tmp_t.find(str(c))
          if check_c != -1:
            cnt = cnt + 1            
print(cnt)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    for i in range(n):
        ans = -1
        for j in range(n):
            if i == j: continue
            ans = max(ans, a[j])
        print(ans)

main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    a_copy = sorted(a)
    a_max = a_copy[-1]
    a_second = a_copy[-2]
    for i in range(n):
        if a[i] == a_max:
            print(a_second)
        else:
            print(a_max)


main()
### BUGGY CODE ###

N = int(input())
gA, sA, bA = map(int, input().split())
gB, sB, bB = map(int, input().split())

#[重さ,価値]を要素とする配列
lstAB_2 = [[gA, gB-gA], [sA, sB-sA], [bA, bB-bA]]
lstBA_2 = [[gB, gA-gB], [sB, sA-sB], [bB, bA-bB]]
lstAB = []
for i in range(3):
    if lstAB_2[i][1] > 0:
        lstAB += [lstAB_2[i]]  

lstBA = []
for i in range(3):
    if lstBA_2[i][1] > 0:
        lstBA += [lstBA_2[i]]

dp = [[0] * (N+1) for _ in range(len(lstAB)+1)]
for i in range(len(lstAB)):
    for j in range(N+1):
        if j < lstAB[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-lstAB[i][0]]+lstAB[i][1])

N += dp[len(lstAB)][N]
# print (N)

dp2 = [[0] * (N+1) for _ in range(len(lstBA)+1)]
for i in range(len(lstBA)):
    for j in range(N+1):
        if j < lstBA[i][0]:
            dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = max(dp2[i][j], dp2[i+1][j-lstBA[i][0]]+lstBA[i][1])
print (N + dp2[len(lstBA)][N])


### FIXED CODE ###

N = int(input())
gA, sA, bA = map(int, input().split())
gB, sB, bB = map(int, input().split())

#[重さ,価値]を要素とする配列
lstAB_2 = [[gA, gB-gA], [sA, sB-sA], [bA, bB-bA]]
lstBA_2 = [[gB, gA-gB], [sB, sA-sB], [bB, bA-bB]]
lstAB = []
for i in range(3):
    if lstAB_2[i][1] > 0:
        lstAB += [lstAB_2[i]]  

lstBA = []
for i in range(3):
    if lstBA_2[i][1] > 0:
        lstBA += [lstBA_2[i]]

dp = [[0] * (N+1) for _ in range(len(lstAB)+1)]
for i in range(len(lstAB)):
    for j in range(N+1):
        if j < lstAB[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-lstAB[i][0]]+lstAB[i][1])

N += dp[len(lstAB)][N]
# print (N)

dp2 = [[0] * (N+1) for _ in range(len(lstBA)+1)]
for i in range(len(lstBA)):
    for j in range(N+1):
        if j < lstBA[i][0]:
            dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = max(dp2[i][j], dp2[i+1][j-lstBA[i][0]]+lstBA[i][1])
print (N + dp2[len(lstBA)][N])
### BUGGY CODE ###

num = input().split()
participant = int(num[0])
init_point = int(num[1])
correct = int(num[2])

tmp = [init_point]*participant

for i in range(correct):
  answer_person = int(input())
  tmp[answer_person-1] += 1
  tmp = [i-1 for i in tmp]
  
for item in tmp:
  if item>0: print("Yes")
  else: print("No")

### FIXED CODE ###

import sys

num = input().split()
participant = int(num[0])
init_point = int(num[1])
correct = int(num[2])

tmp = [0]*participant

for i in range(correct):
  answer_person = int(input())-1
  tmp[answer_person] += 1

for i in tmp:
  if i<=correct-init_point:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

import re

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = []
r = []
for i in range(Q):
    l_i, r_i = [int(item) for item in re.split(r"\s", input())]
    l.append(l_i)
    r.append(r_i)

# ACの場所を探す
p_list = [0] * (N - 1)
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i] = 1
        i += 2
    else:
        i += 1

out_list = []
for q in range(Q):
    # qに答える
    l_i = l[q] - 1
    r_i = r[q] - 1
    out_list.append(str(sum(p_list[l_i:r_i])))

print("\n".join(out_list))


### FIXED CODE ###

import re
import numpy as np

N, Q = [int(item) for item in re.split(r"\s", input())]
S = input()

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = [int(item) for item in re.split(r"\s", input())]

# ACの場所を探す
p_list = [0] * (N + 1)
i = 0
while i < N - 1:
    if S[i:i + 2] == "AC":
        p_list[i + 1] = 1
        i += 2
    else:
        i += 1


cumsum = np.cumsum(p_list)

out_list = []
for q in range(Q):
    # qに答える
    l_i = l[q] - 1
    r_i = r[q] - 1

    if l_i >= 0:
        c_l = cumsum[l_i]
    else:
        c_l = 0
    c_r = cumsum[r_i]
    out_list.append(str(c_r - c_l))

print("\n".join(out_list))
### BUGGY CODE ###

N, A = map(int, input().split())
x = [int(_) for _ in input().split()]
M = 2500
dp = [[[0]*(N+1) for _ in range(M+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(1, N+1):
    for j in range(M+1):
        for k in range(i+1):
            dp[i][j][k] = dp[i-1][j][k]
            if j >= x[i-1] and k > 0:
                dp[i][j][k] += dp[i-1][j-x[i-1]][k-1]

ans = 0
for i in range(1, N+1):
    ans += dp[N][A*i][i]

print(ans)

### FIXED CODE ###

N, A = map(int, input().split())
x = [int(_) for _ in input().split()]
M = 2500
dp = [[[0]*(N+1) for _ in range(M+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(1, N+1):
    for j in range(M+1):
        for k in range(i+1):
            dp[i][j][k] = dp[i-1][j][k]
            if j >= x[i-1] and k > 0:
                dp[i][j][k] += dp[i-1][j-x[i-1]][k-1]

ans = 0
for i in range(1, N+1):
    ans += dp[N][A*i][i]

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

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    a = [list(input()) for i in range(h)]
    queue = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                queue.append([i, j])

    visited = [[-1 for i in range(w)] for j in range(h)]
    ans = 0
    nqueue = []
    while queue:
        x, y = queue.pop(0)
        visited[x][y] = 1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = x + i
            ny = y + j
            if nx >= 0 and ny >= 0 and nx < h and ny < w:
                if visited[nx][ny] == -1 and a[nx][ny] != "#":
                    nqueue.append([nx, ny])
                    visited[nx][ny] = 1
                    a[nx][ny] = "#"
        
        if len(queue) == 0:
            queue = nqueue
            nqueue = []
            ans += 1
        
    print(ans-1)


        
                





if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    a = [list(input()) for i in range(h)]
    queue = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                queue.append((i, j))

    visited = [[-1 for i in range(w)] for j in range(h)]
    ans = 0
    nqueue = deque()
    while queue:
        x, y = queue.popleft()
        visited[x][y] = 1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = x + i
            ny = y + j
            if nx >= 0 and ny >= 0 and nx < h and ny < w:
                if visited[nx][ny] == -1 and a[nx][ny] != "#":
                    nqueue.append([nx, ny])
                    visited[nx][ny] = 1
                    a[nx][ny] = "#"
        
        if len(queue) == 0:
            queue = nqueue
            nqueue = deque()
            ans += 1
        
    print(ans-1)

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

n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
a=1
b=1
x=min(n*m-2,k-2)
for i in range(x):
    a=a*(n*m-2-i)
    b=b*(i+1)
ans=(ans*a//b)%INF
print(ans)


### FIXED CODE ###

n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+(m+d)*m*(m-1)-M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+(m+d)*m*(m-1)-M
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)
### BUGGY CODE ###

from pprint import pprint
import numpy as np
n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]

dp=[[0]*(w+1) for i in range(n+1)]


for i in range(n):
      #print("重さ：{}".format(wsum))
  for wsum in range(1,w+1):
    #print("i={}".format(i))
    if wsum >= wv[i][0]:
        #print("選ぶ, (重さ：{}, 価値：{})".format(wl[i], vl[i]))
        dp[i+1][wsum] = max(dp[i+1][wsum], dp[i][wsum-wv[i][0]]+wv[i][1])
    else:
      dp[i+1][wsum] = dp[i][wsum]
    #pprint(dp)

dp=np.array(dp)
print(np.max(dp))
      

### FIXED CODE ###

from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for wsum in range(1,w+1):
  	#print("i={}".format(i))    
    for i in range(n):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
        else:
          dp[i+1][wsum] = dp[i][wsum]
          
      else:
        dp[i+1][wsum] = dp[i][wsum]
  #print(dp)
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]
#print(wl)
#print(vl)
Knapsack1(n,w,wl,vl)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
 
dp = [float('inf') for _ in range(n)]
dp[0] = 0
 
for i in range(1, n):
  for j in range(max(0, i-k), i):
    dp[i] = min(dp[i], dp[j] + abs(nums[i]-nums[j]))
print(dp[-1])

### FIXED CODE ###

n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
 
dp = [float('inf') for _ in range(n)]
dp[0] = 0
 
for i in range(1, n):
  for j in range(max(0, i-k), i):
    dp[i] = min(dp[i], dp[j] + abs(nums[i]-nums[j]))
print(dp[-1])
### BUGGY CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = float("inf")
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]

for q in range(Q):
    x = int(input())
    ans = INF
    a_i = bisect.bisect_right(s, x)
    b_i = bisect.bisect_right(t, x)
    for a in [s[a_i], s[a_i - 1]]:
        for b in [t[b_i], t[b_i - 1]]:
            ans = min(ans, abs(x - a) + abs(b - a), abs(x - b) + abs(b - a))
    print(ans)

### FIXED CODE ###

import bisect

A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

for x in X:
    ans = float('inf')
    if x < S[0]:
        right_S = S[0]
        left_S = None
    elif x > S[-1]:
        right_S = None
        left_S = S[-1]

    else:
        index_right_S = bisect.bisect_right(S, x)
        if index_right_S < A and S[index_right_S] == x:
            left_S = x
            right_S = x
        else:
            if index_right_S - 1 >= 0:
                left_S = S[index_right_S - 1]
            if index_right_S < A:
                right_S = S[index_right_S]

    if x < T[0]:
        right_T = T[0]
        left_T = None
    elif x > T[-1]:
        right_T = None
        left_T = T[-1]

    else:
        index_right_T = bisect.bisect_right(T, x)
        if index_right_T < B and T[index_right_T] == x:
            left_T = x
            right_T = x
        else:
            if index_right_T - 1 >= 0:
                left_T = T[index_right_T - 1]
            if index_right_T < B:
                right_T = T[index_right_T]

    if left_T and right_S:
        ans = min(ans, abs(left_T - x) + abs(left_T - right_S),
                                   abs(right_S - x) + abs(left_T - right_S))

    if left_T and left_S:
        ans = min(ans, abs(left_T - x) + abs(left_T - left_S),
                                  abs(left_S - x) + abs(left_T - left_S))

    if right_T and left_S:
        ans = min(ans, abs(right_T - x) + abs(right_T - left_S),
                                   abs(left_S - x) + abs(right_T - left_S))

    if right_T and right_S:
        ans = min(ans, abs(right_T - x) + abs(right_T - right_S),
                                  abs(right_S - x) + abs(right_T - right_S))

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

def main():
    import sys
    sys.setrecursionlimit(10**7)
    import collections
    dic=collections.defaultdict(list)

    N,M=list(map(int,sys.stdin.readline().split()))
    for i in range(M):
        x,y=list(map(int,sys.stdin.readline().split()))
        dic[x].append(y)


    dp=[0]*(N+1)
    def dfs(frm):
        if dp[frm]:
            return dp[frm]

        mx=0
        if frm not in dic.keys():
            return 0

        for val in dic[frm]:
            mx=max(mx,dfs(val)+1)
        return mx

    mx=0
    for key in dic.keys():
        mx=max(mx,dfs(key))

    return mx

print(main())

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**7)

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(N)]
    for i in range(M):
        x,y=list(map(int,sys.stdin.readline().split()))
        dic[x-1].append(y-1)


    dp=[0]*(N)
    def dfs(frm):
        if dp[frm]:
            return dp[frm]

        mx=0
        if not dic[frm]:
            return 0

        for val in dic[frm]:
            mx=max(mx,dfs(val)+1)

        dp[frm]=mx
        return mx

    mx=0
    for key in range(N):
        mx=max(mx,dfs(key))

    return mx

print(main())
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

K = int(input())
if K % 2 == 0:
    print(-1)
    exit()

ans = 1
seven = 7
mod = 7 % K
while True:
    if seven % K == 0:
        break
    ans += 1
    seven = (seven % K) * 10 + mod
print(ans)

### FIXED CODE ###

K = int(input())

x = 7
ans = 1
for i in range(K + 1):
    if x % K == 0:
        print(ans)
        exit()
    x = (x * 10 + 7) % K
    ans += 1
print(-1)
### BUGGY CODE ###

INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist


def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    dist = bf.bellmanford(0,N,E)
    ans = dist[-1]
    neg = [False for _ in range(N)]
    for l in range(N):
        for e in E:
            a,b,c = e
            if dist[a] == INF:continue
            if dist[b] > dist[a]+c:
                neg[b] = True
            if neg[a]:
                neg[b] = True
    if neg[-1]:
        print("inf")
    else:
        print(-ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    if i == V-1 and v == V-1:
                        return -1
        return dist
    

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    dist = bf.bellmanford(0,N,E)
    if dist == -1:
        print('inf')
    else:
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()