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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  s=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):
      if s[i][j]=='#':
        continue

      _ans=-1
      for a in range(i)[::-1]:
        if s[a][j]=='.':
          _ans+=1
        else:
          break
      for a in range(i,h):
        if s[a][j]=='.':
          _ans+=1
        else:
          break
      for a in range(j)[::-1]:
        if s[i][a]=='.':
          _ans+=1
        else:
          break
      for a in range(j,w):
        if s[i][a]=='.':
          _ans+=1
        else:
          break

      ans=max(ans,_ans)
  return ans

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  s=[S() for _ in range(h)]

  L=[[0 for _ in range(w)]for __ in range(h)]
  R=[[0 for _ in range(w)]for __ in range(h)]
  D=[[0 for _ in range(w)]for __ in range(h)]
  U=[[0 for _ in range(w)]for __ in range(h)]

  for i in range(h):
    for j in range(w):
      if s[i][j]=='#':
        L[i][j]=0
        U[i][j]=0
        continue

      if i==0:
        U[i][j]=1
      else:
        U[i][j]=U[i-1][j]+1

      if j==0:
        L[i][j]=1
      else:
        L[i][j]=L[i][j-1]+1

  for i in range(h)[::-1]:
    for j in range(w)[::-1]:
      if s[i][j]=='#':
        R[i][j]=0
        D[i][j]=0
        continue

      if i==h-1:
        D[i][j]=1
      else:
        D[i][j]=D[i+1][j]+1

      if j==w-1:
        R[i][j]=1
      else:
        R[i][j]=R[i][j+1]+1

  ans=0
  # print(R,L,D,U)
  for i in range(h):
    for j in range(w):
      ans=max(ans,R[i][j]+L[i][j]+U[i][j]+D[i][j]-3)

  return ans

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

n = int(input())
ans = 1 
a = list(map(int,input().split()))
for i in range(n):
  ans *= a[i]
if ans > 10**18:
  print("-1")
else:
  print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in a:
    ans = 0
else:
    for i in a:
        ans *= i
        if(ans > 10**18):
            ans = -1
            break
print(ans)
### BUGGY CODE ###

import sys

n, m = list(map(int, input().split()))
a_list = []
b_list = []
for i in range(m):
    a, b = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
ab = zip(a_list,b_list)

cand_b = []
for a, b in ab:
    if a == 1:
        cand_b.append(b)

ab = zip(a_list,b_list)
for a, b in ab:
    if a in cand_b and b == n:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')


### FIXED CODE ###

import sys

n, m = list(map(int, input().split()))
mid_set1 = set([])
mid_set2 = set([])

for i in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        mid_set1.add(b)
    elif b == n:
        mid_set2.add(a)

if len(mid_set1&mid_set2) > 0:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        pre = post
        post = []
        for j in pre:
            post.append(j+l[i])
            post.append(j-l[i])
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        if l[i]:
            pre = sorted(post)
            post = []
            for j in range(len(pre)):
                if j==0 or pre[j] != pre[j-1]:
                    post.append(pre[j]+l[i])
                    post.append(pre[j]-l[i])
            # print(pre, post)
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N,M=map(int,input().split())
price_list=sorted([int(item) for item in input().split()])
total_m=0
def discount(price_list,tickets_num):
    total_ticket =0
    price_list.sort(reverse=True)

    while total_ticket < tickets_num:
        temp = price_list.pop(0)
        temp_new=temp//2
        price_list.append(temp_new)
        price_list.sort(reverse=True)
        total_ticket+=1
    return price_list

res = discount(price_list,M)
print(sum(res))


### FIXED CODE ###

import heapq as hp
N,M=map(int,input().split())
price_list=sorted([-1*int(item) for item in input().split()])
total_m=0
def discount(price_list,tickets_num):
    total_ticket =0
    hp.heapify(price_list)

    while total_ticket < tickets_num:
        temp = hp.heappop(price_list)
        hp.heappush(price_list,-1*(-1*temp//2))
        total_ticket+=1
    return price_list

res = discount(price_list,M)
print(-1*sum(res))
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                if j - i != k - j:
                    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')
all = r * g * b

sub = 0
for i in range(N-1):
    for j in range(i, N):
        k = 2 * j - i
        if k > N - 1:
            break
        if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            sub += 1
print(all - sub)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

#１回のクエリで半分に空席がある場所を絞る
end = ri() - 1
print(0, flush=True)
S = rs()[0]
if S == 'V':
    exit()
start = 0
cur = S
for _ in range(19):
    target = start + max(2, (end - start) // 4 * 2)
    print(target, flush=True)
    s = rs()[0]
    if s == 'V':
        exit()
    if cur != s:
        end = target
    else:
        start = target
print(start + 1, flush=True)
s = rs()[0]
if s == 'V':
    exit()
else:
    print(start + 2, flush=True):
    exit()
#24


### FIXED CODE ###

N = int(input())

def ask(n):
    print(n, flush=True)
    resp = input().rstrip()[0]
    if resp == 'V':
        exit()
    return resp

def condition(L,R,resp_L,resp_R):
    if (R-L)&1:
        return resp_L == resp_R
    else:
        return resp_L != resp_R

resp = ask(0)

L = 0
R = N
resp_L = resp
resp_R = resp
for _ in range(19):
    M = (L + R) // 2
    resp_M = ask(M)
    if condition(L,M,resp_L,resp_M):
        R,resp_R = M,resp_M
    else:
        L,resp_L = M,resp_M
### BUGGY CODE ###

import math
a, b, n = map(int, input().split())
ans = 0
for i in range(n+1):
  ans = max(ans, math.floor(a*i/b)-a*math.floor(i/b))
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
ans = 0
e = min(n+1,b)
s = max(int(b/a),e-1000)
for i in range(s, e):
  x = (int(a*i/b)-a*int(i/b))
  if ans < x:
    ans = x
print(ans)
### BUGGY CODE ###

get_num=int(input())
get_list=[]
count=0

for i in range(get_num):
    tmp=input()
    if (tmp in get_list)==False:
        get_list.append(tmp)
        count+=1;
    
print(count)

### FIXED CODE ###

get_num=int(input())
get_list=[]
count=0

for i in range(get_num):
    tmp=input()
    get_list.append(tmp)

list=list(set(get_list))
    
print(len(list))
### BUGGY CODE ###

import sys
import time
def solve(matrix):
    N = len(matrix)
    #print  matrix
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    start = time.time()
    while remaining:
        prev = remaining
        day+=1
        #print "day %d" % day
        #print "matrix: %r" % matrix
        #print "remaining:%d" % remaining
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                #print "%d and %d" % (x, y)
                #print "matrix: %r" % matrix
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                #print 'match: %r' % match
        if time.time() - start > 1.6:
            print worst
            return
        if remaining  == prev:
            print -1
            return
    print day



N = raw_input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in raw_input().split()])
solve(matrix)

### FIXED CODE ###

import sys
import time
def solve(matrix):
    N = len(matrix)
    #print  matrix
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    start = time.time()
    while remaining:
        prev = remaining
        day+=1
        #print "day %d" % day
        #print "matrix: %r" % matrix
        #print "remaining:%d" % remaining
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                #print "%d and %d" % (x, y)
                #print "matrix: %r" % matrix
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                #print 'match: %r' % match
        if time.time() - start > 1.5:
            print worst
            return
        if remaining  == prev:
            print -1
            return
    print day



N = raw_input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in raw_input().split()])
solve(matrix)
### BUGGY CODE ###

N=int(input())

xy = []
for _ in range(N):
  x,y=map(int,input().split())
  xy.append((x,y))
M,m = 3*(10**9), -3*(10**9)
x_max, x_min, y_max, y_min, t_max, t_min = m,M,m,M,m,M
cand = [xy[0] for _ in range(6)]
for x,y in xy[1:]:
  if x > x_max: x_max = x; cand[0]=(x,y);
  if x < x_min: x_min = x; cand[1]=(x,y);
  if y > y_max: y_max = y; cand[2]=(x,y);
  if y < y_min: y_min = y; cand[3]=(x,y);
  if x+y > t_max: t_max = x+y; cand[4]=(x,y);
  if x+y < t_min: t_min = x+y; cand[5]=(x,y);

ans = 0
for i in range(N-1):
  x1,y1 = xy[i]
  for j in range(i+1,N):
    x2,y2 = xy[j]
    ans = max(ans, abs(x1-x2)+abs(y1-y2))
print(ans)

### FIXED CODE ###

N=int(input())

xy = []
d0, d1 = [],[]
for _ in range(N):
  x,y=map(int,input().split())
  d0.append(x-y)
  d1.append(x+y)
print(max(max(d0)-min(d0), max(d1)-min(d1)))
### BUGGY CODE ###

n = int(input())
P = [int(x) for x in input().split()]

counter = 1
for i in range(1,n):
    for x in P[0:i]:
        if P[i]>x:
            break
    else:
        counter +=1

print(counter)

### FIXED CODE ###

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

minimum = float('inf')
ans = 0
for p in P:
    if p <=minimum:
        minimum = p
        ans += 1
print(ans)
### BUGGY CODE ###

import heapq as hq
def solve():
    N, M = list(map(int, input().split()))
    plan = []
    for _ in range(N):
        plan.append(list(map(int, input().split())))
    task = {}
    for p in plan:
      if p[0] in task.keys():
        task[p[0]].append(-p[1])
      else:
        task[p[0]] = [-p[1]]
    choices = []
    res = 0
    d = task.keys()
    for day in range(1, M+1):
        if day in d:
            choices.extend(task[day])
            hq.heapify(choices)
        if len(choices) > 0:
            res += - hq.heappop(choices)
    print(res)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import heapq as hq
def solve():
    N, M = list(map(int, input().split()))
    plan = []
    for _ in range(N):
        plan.append(list(map(int, input().split())))
    task = {}
    for p in plan:
      if p[0] in task.keys():
        task[p[0]].append(-p[1])
      else:
        task[p[0]] = [-p[1]]
    choices = []
    res = 0
    d = task.keys()
    for day in range(1, M+1):
        if day in d:
            for j in task[day]:
                hq.heappush(choices, j)
        if len(choices) > 0:
            res += - hq.heappop(choices)
    print(res)

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

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])
### BUGGY CODE ###

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

ans = []
count = 0
for i in range(N):
    for j in range(i + count, N):
        if (j == N - 1):
            ans.append(count)
            count = 0
            break
        if (H[j] < H[j + 1]):
            ans.append(count)
            count = 0
            break
        else:
            count += 1

print(max(ans))


### FIXED CODE ###

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

ans = []
count = 0
for j in range(N):
    if (j == N - 1):
        ans.append(count)
        count = 0
        break
    if (H[j] < H[j + 1]):
        ans.append(count)
        count = 0
        continue
    elif (H[j] >= H[j + 1]):
        count += 1

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

import math
n = int(input())
a_tmp = input().split()
a = []
for i in range(n):
    a.append(int(a_tmp[i]))
a1 = []
for i in range(n):
    a1.append(a[i]-1-i)
b_max = max(a1)
b_min = min(a1)
sadness = []
for b in range(b_min, b_max+1):
    abs = [math.fabs(a1[i]-b) for i in range(n)]
    sadness.append(int(sum(abs)))
print(min(sadness))


### FIXED CODE ###

import math
n = int(input())
a_tmp = input().split()
a_tmp1 = []
for i in range(n):
    a_tmp1.append(int(a_tmp[i])-i-1)
a = sorted(a_tmp1)
if n % 2 == 0:
    x = a[n//2]
else:
    x = a[n//2]
ans = 0
for _ in a:
    ans += math.fabs(_ - x)
print(int(ans))
### BUGGY CODE ###

N = int(input())
S = input()

cnt = 0
for i in range(1000):
  c = [i // 100, (i // 10) % 10, i % 10]
  f = 0
  for j in range(N):
    if S[j] == str(c[f]):
      f += 1
    if f == 3:
      break
  if f == 3:
    cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
S = input()

cnt = 0
for i in range(1000):
  c = str(i).zfill(3)
  if c[0] in S:
        index1 = S.index(c[0])
        if c[1] in S[index1+1:]:
            index2 = index1 + 1 + S[index1+1:].index(c[1])
            if c[2] in S[index2+1:]:
                cnt+=1
print(cnt)
### BUGGY CODE ###

import sys

def dijkstra(m, start, goal, matrix):
  defnode = {}
  cost = [sys.maxint] * (m+1)
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in xrange(1, m+1):
      if i in defnode:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(1, m+1):
      if i in defnode:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    if minnode == goal:
      print cost[goal]
      return
    node = minnode

while True:
  n, m = map(int, raw_input().split())
  if n == 0 and m == 0:
    break
  cost = [[sys.maxint] * (m+1) for j in xrange(m+1)]
  time = [[sys.maxint] * (m+1) for j in xrange(m+1)]
  for i in xrange(n):
    a, b, c, t = map(int, raw_input().split())
    cost[a][b] = c
    cost[b][a] = c
    time[a][b] = t
    time[b][a] = t
  k = int(raw_input())
  for i in xrange(k):
    p, q, r = map(int, raw_input().split())
    if r == 0:
      dijkstra(m, p, q, cost)
    else:
      dijkstra(m, p, q, time)

### FIXED CODE ###

import sys

def dijkstra(m, start, goal, matrix):
  defnode = [False] * (m+1)
  cost = [sys.maxint] * (m+1)
  cost[start] = 0
  node = start
  while True:
    defnode[node] = True
    for i in xrange(1, m+1):
      if defnode[i]:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(1, m+1):
      if defnode[i]:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    if minnode == goal:
      print cost[goal]
      return
    node = minnode

while True:
  n, m = map(int, raw_input().split())
  if n == 0 and m == 0:
    break
  cost = [[sys.maxint] * (m+1) for j in xrange(m+1)]
  time = [[sys.maxint] * (m+1) for j in xrange(m+1)]
  for i in xrange(n):
    a, b, c, t = map(int, raw_input().split())
    cost[a][b] = c
    cost[b][a] = c
    time[a][b] = t
    time[b][a] = t
  k = int(raw_input())
  for i in xrange(k):
    p, q, r = map(int, raw_input().split())
    if r == 0:
      dijkstra(m, p, q, cost)
    else:
      dijkstra(m, p, q, time)
### BUGGY CODE ###

N = int(input())
L_list = list(map(int,input().split()))
ans = 0
L_list.sort()

for i in range(N-2):
    J = i+1
    for x in range(N-i-1):
        j = J+x
        K = j+1
        for y in range(N-j-1):
            k = K+y
            if L_list[i] + L_list[j] > L_list[k]:
                ans += 1
            else:
                break

print(ans)

### FIXED CODE ###

import bisect

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

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        insert_index = bisect.bisect_left(l, l[i] + l[j],j) #l[i] + l[j]を挿入できる点を探す。同じ者がlにすでにある時は、一番左になるようにする
        ans += (insert_index - j - 1)

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

n=int(input())
l=list(map(int,input().split(" ")))
c=0
for i in range(n):
  for j in range(i+1,n):
    if l[i]+l[j]==j-i:
      c+=1
      
print(c)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N = int(input())

A = list(map(int, input().split()))
Ap = [i - A[i] for i in range(N)]
Ap.sort()

ans = 0
for i in range(N):
	ans += bisect_right(Ap, i + A[i]) - bisect_left(Ap, i + A[i])

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

def lensetlist(A):
    B = []
    for i in A:
        if i not in B:
            B.append(i)
    return len(B)

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

for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

used = [0 for i in range(N)]
result = []
stack = []
ans = 0
def path(start, visited):
    if len(visited) == N:
        result.append(visited[:])
        exit
    stack.append(start)
    while len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint in visited:
            continue
        visited.append(nextpoint)
        for i in range(M):
            if A[i] == start:
                path(B[i], visited)
            if B[i] == start:
                path(A[i], visited)
        visited.pop()

path(1, [])
print(lensetlist(result))


### FIXED CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(M):
                if A[i][0] == start:
                    path(A[i][1], visited)
                if A[i][1] == start:
                    path(A[i][0], visited)
            visited.pop()

path(1, [])
result = list(map(list, set(map(tuple, result))))
print(len(result))
### BUGGY CODE ###

n=int(input())
dp=[1]*(n+1)
dp[0]=0
dp[1]=1
c=0
for i in range(2,n+1):
    for j in range(i,n+1,i):
        dp[j]+=1
for i in range(n+1):
    c+=dp[i]*i
print(c)


### FIXED CODE ###

n=int(input())
c=0
ans=0
for i in range(1,n+1):
    c=n//i
    ans+=(c)*(c+1)*(i)//2
print(ans)
### BUGGY CODE ###

#　n以下の整数の素数列挙（エラトステネスの篩）
#-------------------------------------------------------------------------
import numpy as np

def eth(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
#-------------------------------------------------------------------------
import itertools
import sys
input = sys.stdin.buffer.readline

prime = eth(5*10**4)
acu = [0] * ((5*10**4)//2+1)
for i in range(1,(5*10**4)//2+1):
    k = (i-1) * 2 +1
    if k in prime and (k+1)//2 in prime:
        acu[i] = acu[i-1] + 1
    else:
        acu[i] = acu[i-1]

q = int(input())

for i in range(q):
    l,r = map(int,input().split())
    li = (l-1) // 2
    ri = (r-1) // 2
    if ri == li and li in prime:
        print(1)
    else:
        print(acu[ri+1]-acu[li])

### FIXED CODE ###

from itertools import accumulate
# エラトステネスの篩
# is_prime := 1~nが素数か否か
# table := 2~nのうち素数
def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

max_R = max(R)
is_prime, table = sieve(max_R)

check = [0]*(max_R + 1)
for i in range(0, max_R + 1):
    if (i % 2 == 1):
        if (is_prime[i-1] and is_prime[(i+1)//2-1]):
            check[i] = 1

# 累積和
check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print(check[R[i] + 1] - check[L[i]])
### BUGGY CODE ###

def divisor(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0

for i,num in enumerate(A):
    if i > 0 and A[i-1] == num:
        continue
    if not divisor(num) & set(A[i+1:]):
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
dp = [True] * (A[-1]+1)

for i,num in enumerate(A):
    if i < N-1 and A[i+1] == num:
        dp[num] = False
    for j in range(2*num, A[-1]+1, num):
        dp[j] = False

print(len([i for i in A if dp[i]]))