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

import math

mod = 10 ** 9 + 7
n = int(input())
f = math.factorial(n)
l = []
i = 1
while i * i <= f:
    if f % i == 0:
        l.append(i)
        if i != f // i:
            l.append(f // i)
    i += 1
print(pow(len(l), 1, mod))


### FIXED CODE ###

mod = 10 ** 9 + 7
d = {}


def prime_factorizer(n):
    i = 2
    global d
    while i * i <= n:
        if n % i == 0:
            if i in d.keys():
                d[i] += 1
            else:
                d.setdefault(i, 1)
            n //= i
        else:
            i += 1
    if n != 1:
        if n in d.keys():
            d[n] += 1
        else:
            d.setdefault(n, 1)


n = int(input())

for i in range(n, 0, -1):
    prime_factorizer(i)

cnt = 1
for k, v in d.items():
    cnt *= v + 1
print(cnt % mod)
### BUGGY CODE ###

x = int(input())
done=False
for a in range(-10000,10001):
  for b in range(-10000,10001):
    if(not done and a**5-b**5==x):
      print(a,b)
      done=True

### FIXED CODE ###


x = int(input())
for a in range(-300,301):
  if(a<0):
    for b in range(-300,a):
      if(a**5-b**5==x):
        print(a,b)
        break
    else: continue
    break
  else:
    for b in range(-300,a):
      if(a**5-b**5==x):
        print(a,b)
        break
    else: continue
    break
### BUGGY CODE ###

mod = 1000000007
n= int(input())
a= list(map(int,input().split()))
check = [0]*(n+1)
g1=[1,1]
g2=[1,1]
inverse=[0,1]
for i in range(2,n+1+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
def cmb2(n,r):
    mod = 1000000007
    if (r<0 or r>n ):return 0
    r = min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%mod
r=-1
jn=-1
for i in range(n+1):
    check[a[i]-1]+=1
    if check[a[i]-1]==2:
        jn,r=a[i],i
        break
l=a.index(jn)
s = min(l,n-r)
t = max(l,n-r)
print(n)

for p in range(2,n+1):
    w2=cmb2(n+1,p)
    x=p-t-1
    y=s
    yobun=0
    for k in range(max(p-t-1,0),s+1):
      if p-t-1<=k<=s:
        yobun+=cmb2(s,k)*cmb2(t,p-k-1)
    print(((w2+mod)-yobun) % mod)

print(1)


### FIXED CODE ###

mod = 1000000007
n= int(input())
a= list(map(int,input().split()))
check = [0]*(n+1)
g1=[1,1]
g2=[1,1]
inverse=[0,1]
for i in range(2,n+1+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
def cmb2(n,r):
    mod = 1000000007
    if (r<0 or r>n ):return 0
    r = min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%mod
r=-1
jn=-1
for i in range(n+1):
    check[a[i]-1]+=1
    if check[a[i]-1]==2:
        jn,r=a[i],i
        break
l=a.index(jn)
s = min(l,n-r)
t = max(l,n-r)
print(n)
for p in range(2,n+1):
  w2=cmb2(n+1,p)
  y2=cmb2(s+t,p-1)
  print(((w2+mod)-y2) % mod)
print(1)
### BUGGY CODE ###

import itertools
n =  int(input())
L = list(map(int, input().split()))
L_conv = list(itertools.combinations(L, 3))
cnt = 0
for i in L_conv:
    tmp = sorted(i, reverse = True)
    if sum(tmp) > tmp[0] * 2:
        cnt += 1

print(cnt)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
list.sort(l)
cnt = 0

for i in range(n - 1):
    for j in range(i + 1, n):
        a = l[i]
        b = l[j]
        a_b = a + b
        insert_index = bisect.bisect_left(l, a_b)
        cnt += insert_index - (j + 1)

print(cnt)
### BUGGY CODE ###

import sys 
input = sys.stdin.readline
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n,Q=map(int,input().split())
xs,qs,tmp = [],[],set()
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
    tmp.add(x)
for _ in range(Q):
    qs.append(int(input()))

xs.sort()
tmp = list(tmp)
tmp.sort()
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

qi = 0
q = qs[qi]
XN = len(tmp)
st = SegTree([XN]*XN, XN, XN, min)
for t,r,x in xs:
    if q < t:
        c = st.query(0,XN)
        while True:
            if q < t:
                if c != XN:
                    print(tmp[c])
                else:
                    print(-1)
                Q-=1
                if Q == 0:
                    break
                qi += 1
                q = qs[qi]
            else:
                break
#    print(t,r,x)
    if Q==0:
        break
    if r:
        st.update(x2i[x], x2i[x])
    else:
        st.update(x2i[x], XN)
print("-1\n"*Q)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

n,m,q=map(int, input().split())

tab=[[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    l,r=map(int, input().split())
    tab[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n):
        tab[i][j+1]+=tab[i][j]

for _ in range(q):
    p,q=map(int, input().split())
    ans=0
    for i in range(p,q+1):
        ans+=tab[i][q]-tab[i][p-1]
    print(ans)


### FIXED CODE ###

n,m,q=map(int, input().split())

tab=[[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    l,r=map(int, input().split())
    tab[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n):
        tab[i][j+1]+=tab[i][j]

for _ in range(q):
    p,q=map(int, input().split())
    ans=0
    for i in range(p,q+1):
        ans+=tab[i][q]-tab[i][p-1]
    print(ans)
### BUGGY CODE ###

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
A = [a for a,b in AB]
B = [b for a,b in AB]
C = list(range(N))

def val(x):
  return B[x]

def merge(la, lb):
  na = len(la)
  nb = len(lb)
  ans = [None] * (na+nb)
  ia = 0
  ib = 0
  
  while ia<na and ib<nb:
    if val(la[ia]) < val(lb[ib]):
      ans[ia+ib] = la[ia]
      ia += 1
    else:
      ans[ia+ib] = lb[ib]
      ib += 1
      
  if ia<len(la):
    ans[ia+ib:] = la[ia:]
  if ib<len(lb):
    ans[ia+ib:] = lb[ib:]
  return ans
    
def mergeSort(x):
    l = len(x)
    if l <= 1:
        return x
    d = l // 2 
    left = mergeSort(x[:d])
    right = mergeSort(x[d:])
    return merge(left,right)

C = mergeSort(C)

ans = "Yes"
t = 0
for i in range(N):
    t += A[C[i]]
    if t > B[C[i]]:
        ans = "No"

print(ans)



### FIXED CODE ###

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key = lambda x:x[1])

temp_total = 0
for a,b in AB:
  temp_total += a
  if temp_total<=b:
    continue
  else:
    print('No')
    break
else:
  print('Yes')
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split(' ')))
count_list = [A_list.count(i) for i in range(N+1)]
table = [(count**2-count)//2 for count in count_list]
sum_table = sum(table)

for i in range(N):
  print(sum_table - table[A_list[i]] + (count_list[A_list[i]]-1)*(count_list[A_list[i]]-2)//2)

### FIXED CODE ###

import collections

N = int(input())
A_list = list(map(int, input().split(' ')))
count_dict = collections.Counter(A_list)

sum_ = 0
for count in count_dict.values():
  sum_ += (count**2 - count) // 2

for A in A_list:
  print(sum_ - count_dict[A] + 1)
### BUGGY CODE ###

N = int(input())

def make_divisors(n):
	divisors = []
	for i in range(1, int(n**0.5)+1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n//i)
	divisors.sort()
	return len(divisors)

ans = 0
for c in range(1, N):
	ab = N - c
	l = make_divisors(ab)
	ans += l
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1, N):
	ans += (N - 1) // a
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
ans = 0
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
for i in range(p):
    c1 = sum(l[i])
    ans += (2**(p - i - 1)) * c1 * (n - c1)
    ans %= (10**9 + 7)
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    M = max(a)
    p = len(format(M, 'b'))
    l = [0 for _ in range(p)]
    ans = 0
    for i in range(n):
        a_s = format(a[i], '0' + str(p) + 'b')
        for c in range(p):
            if a_s[c] == '1':
                l[c] += 1
    for i in range(p):
        c1 = l[i]
        ans += (2**(p - i - 1)) * c1 * (n - c1)
        ans %= (10**9 + 7)
    print(ans)

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

s=input()
k=int(input())
a=[]
for i in range(len(s)):
    for j in range(i+1, max(i+k, len(s)+1)):
        a.append(s[i:j])
b=list(set(a))
b.sort()
print(b[k-1])


### FIXED CODE ###

s=input()
k=int(input())
substrings=set()
for i in range(len(s)):
    for j in range(5):
        if i+j<len(s):
            substrings.add(s[i:i+j+1])
substrings=sorted(list(substrings))
print(substrings[k-1])
### BUGGY CODE ###

s = input()
q = int(input())
a, b = '', ''
cnt = 0
for _ in range(q):
    que = input().split()
    if que[0] == '1':
        cnt += 1
    else:
        if (cnt+int(que[1])) %2 == 0:
            a += que[2]
        else:
            b += que[2]
if cnt%2 == 1:
    s = s[-1::-1]
    s = a[-1::-1]+s+b
else:
    s = b[-1::-1]+s+a
print(s)

### FIXED CODE ###

s = input()
q = int(input())
a, b = '', ''
cnt = 0
for _ in range(q):
    que = input().split()
    if que[0] == '1':
        cnt += 1
    else:
        if (cnt+int(que[1])) %2 == 0:
            a += que[2]
        else:
            b += que[2]
if cnt%2 == 1:
    s = a[-1::-1]+s[-1::-1]+b
else:
    s = b[-1::-1]+s+a
print(s)
### BUGGY CODE ###

k, s = map(int, input().split())

sum_set = []
for i in range(k + 1):
    for j in range(k + 1):
        for m in range(k + 1):
            if i + j + m == s:
                comb = [i, j, m]
                sum_set.append(comb)
print(len(sum_set))

### FIXED CODE ###

k, s = map(int, input().split())

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            count += 1
print(count)
### BUGGY CODE ###

N = int(input())
li = list(map(int,input().split()))
A = 1
i = 0
if 0 in li:
  print(0)
else:
    for i in range (N):
      A = A * li[i]
      i += 1
    if A <= 1000000000000000000:
        print(A)
    else: 
        print (-1)

### FIXED CODE ###

N = int(input())
li = list(map(int,input().split()))
A = 1
i = 0
B = 0
if 0 in li:
  print(0)
else:
    for i in range (N):
      A = A * li[i]
      if (A > 10**18):
        break
      else: 
        B += 1
        i += 1
    if B == N:
      print (A)
    else:
      print (-1)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split(' ')))
count_dict = {}
for A in A_list:
  strA = str(A)
  if strA in count_dict.keys():
    pass
  else:
    count_dict[strA] = A_list.count(A)
#print(count_dict)

sum_ = 0
for count in count_dict.values():
  sum_ += (count**2 - count) // 2

for A in A_list:
  print(sum_ - count_dict[str(A)] + 1)

### FIXED CODE ###

import collections

N = int(input())
A_list = list(map(int, input().split(' ')))
count_dict = collections.Counter(A_list)

sum_ = 0
for count in count_dict.values():
  sum_ += (count**2 - count) // 2

for A in A_list:
  print(sum_ - count_dict[A] + 1)
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline().rstrip())
As = list(map(int, sys.stdin.readline().rstrip().split()))

ans = 0
for i in range(N - 1):
    if As[i] > N:
        continue
    for j in range(i, N):
        if As[j] > N:
            continue
        x = j - i
        if As[i] + As[j] == x:
            ans += 1

print(ans)

### FIXED CODE ###

import sys
from collections import Counter

N = int(sys.stdin.readline().rstrip())
As = list(map(int, sys.stdin.readline().rstrip().split()))

ll = [0] * N
lr = [0] * N
for i, a in enumerate(As):
    ll[i] = i + a
    lr[i] = i - a

cl = Counter(ll)
cr = Counter(lr)

ans = 0
for l in cl.keys():
    ans += cl[l] * cr[l]

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

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

for h in range(Q):
    count=0
    word=[]
    for k in range(L[h]-1,R[h]):
        word.append(S[k])
        continue
    
    for g in range(len(word)-1):
        if word[g]=='A' and word[g+1]=='C':
            count+=1
        continue
    print(count)
    continue
    

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
c=[0]
t=0
for i in range(1,n):
    t+=1 if (s[i-1]=='A' and s[i]=='C') else 0
    c.append(t)
for i in range(q):
    l,r=map(int,input().split())
    print(c[r-1]-c[l-1])
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans *= i
    
print(ans % (10 ** 9 + 7))

### FIXED CODE ###

N = int(input())
pow = 1
num = 10**9+7
for i in range(1,N+1):
  pow = pow*i%num
print(pow%num)
### BUGGY CODE ###

def dijkstra(startNode, nodeNum, edgeNum, cost):
    '''
    startNodeから各頂点への最短距離をダイクストラ法で計算
    startNode:始点
    nodeNum:ノードの数
    edgeNum:エッジの数
    cost[a][b]:ab間の距離
    '''
    d = [float('inf')]*nodeNum
    x = [0]*nodeNum
    usedNode = [False]*nodeNum
    d[startNode] = 0
    
    while True:
        v = -1
        y = 0
        for i in range(n):
            if (not usedNode[i]) and (v == -1):
                v=i
                y=i+1
            elif (not usedNode[i]) and d[i] < d[v]:
                v=i
                y=i+1
        if v == -1:
            break
        usedNode[v] = True

        for j in range(n):
            if d[j] > d[v]+cost[v][j]:
                d[j] = d[v]+cost[v][j]
                x[j] = y
    return d,x


n, m = map(int, input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
for i in range(m):
    a[i], b[i] = map(int, input().split())

c = [[float('inf') for i in range(n)] for j in range(n)]
for i in range(m):
    c[a[i-1]-1][b[i-1]-1] = 1
    c[b[i-1]-1][a[i-1]-1] = 1

d,x = dijkstra(0, n, m, c)

print('Yes')
for i in range(n-1):
    print(x[i+1])


### FIXED CODE ###

# 入力
N, M = map(int, input().split()) # ノード数, エッジ数
edges = [[] for i in range(N)] # エッジ
for i in range(M):
    A, B = map(int, input().split())
    edges[A - 1] += [B - 1]
    edges[B - 1] += [A - 1]

# 幅優先探索
que = [0] # 探索用キュー
ans = [0] + [-1 for i in range(N - 1)] # 未探索ノード 兼 道しるべ
while -1 in ans: # 未探索ノードがある間
    quetmp = que
    que = []
    for node in quetmp: # 探索キュー内のノードに対して
        for neighbor in edges[node]: # 全ての隣接ノードに対して
            if ans[neighbor] == -1: # 未探索なら
                ans[neighbor] = node + 1 # 道しるべを設定
                que += [neighbor] # キューに入れる

# 出力
print('Yes')
for a in ans[1:]:
    print(a)
### BUGGY CODE ###

import math
import sys
from decimal import Decimal, ROUND_HALF_UP
N = int(input())
A_list = list(map(str,input().split()))
B_list = []

if '0' in A_list:
  print('0')
  sys.exit()
  
else:
  for i in range(N):
    logA = Decimal(A_list[i]).log10()
    B_list.append(logA)

sum = 0
for j in range(N):
  sum += B_list[j]

if sum > 18:
  print('-1')
else:
  pro = 10**sum
  print(Decimal(str(pro)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))

### FIXED CODE ###

import sys
N = int(input())
A_list = list(map(int,input().split()))
border = 10**18

if 0 in A_list:
  print(0)
  sys.exit()
else:
  A_list.sort(reverse=True)
  pro = 1
  for i in range(N):
    pro *= A_list[i]
    if pro > 10**18:
      print('-1')
      sys.exit()
    else:
      pass

print(pro)
### BUGGY CODE ###

# A = input()
# A = int(input())
# A = map(int, input().split())
# A = list(map(int, input().split()))
# A = [int(input()) for i in range(N)]
#
# c = collections.Counter()

import collections

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

ma = sum(p[:K])
kukan = sum(p[:K])
idx = 0
for i in range(N - K):
  kukan = kukan - p[i] + p[i+K]
  if ma < kukan:
    ma = kukan
    idx = i+1

exp = 0
for i in range(idx, K+idx):
  exp_1 = 0
  for j in range(1, p[i]+1):
    exp_1 += j
  exp += exp_1 / p[i]

print(exp)



### FIXED CODE ###

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k  = map(int, input().split())
p  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

q = sum(p[:k])
max_ = (q, 0, k)
for i in range(k, n):
    q = q + p[i] - p[i-k]
    if max_[0] < q:
        max_ = (q, i-k+1, i+1)

ans = 0
for p_ in p[max_[1]:max_[2]]:
    ans += 1 + (p_ - 1) * 0.5

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

n,m=map(int,input().split())

py=[]
#初期値が0の辞書

p2year = [[] for _ in range(n+1)]

for _ in range(m):
    p,y=map(int,input().split())
    py.append((p,y))
    p2year[p].append(y)


for item in range(n+1):
    p2year[item].sort()

for item in py:
    pp=item[0]
    yy=item[1]
    result=str(pp).zfill(6)+str((p2year[pp].index(yy)+1)).zfill(6)
    print(result)



### FIXED CODE ###

n,m=map(int,input().split())

py=[]
#初期値が0の辞書

p2year = [[] for _ in range(n+1)]

for _ in range(m):
    p,y=map(int,input().split())
    py.append((p,y))
    p2year[p].append(y)

#初期値が0の辞書
from collections import defaultdict
py2index = defaultdict(lambda: 0) 

for item in range(n+1):
    p2year[item].sort()
    for index,temp in enumerate(p2year[item]):
        py2index[(item,temp)]=index+1

for item in py:
    pp=item[0]
    yy=item[1]
    result=str(pp).zfill(6)+str((py2index[(pp,yy)])).zfill(6)
    print(result)
### BUGGY CODE ###

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

    sum = 0
    for i in range(0, N - 1):
        for j in range(i + 1, N):
            sum += (A[i] * A[j])
    sum = sum % (10 ** 9 + 7)

    print(sum)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

    B = sum(A)
    answer = 0
    for i in range(0, N):
        answer += A[i] * (B - A[i])
        B -= A[i]

    answer %= (10 ** 9 + 7)

    print(answer)


if __name__ == "__main__":
    main()

# A1*A2 + A1*A3 + ... + A1*AN = A1 * (A2 + A3 + ... + AN)
# +
# A2*A3 + A2*A4 + ... +| A2*AN = A2 * (A3 + A4 + ... + AN)
### BUGGY CODE ###

S = input()
size = len(S)
ans = 0#[]
def check(target):
  if int(target) % 2019 == 0:
    return True
  else:
    return False
  
for i in range(size-3):
  for j in range(4,size+1):
    if i+j > size:
      continue
    t = S[i:i+j]
    if check(t):
      ans += 1
      #ans.append((i+1,i+j))
print(ans)

### FIXED CODE ###

S = input()
size = len(S)
ans = 0
d = [0]*2019
pre = ''
ln = 0
v = 1
  
for i in range(1,size+1):
  md = (ln +(int(S[-1*i])*v))%2019
  d[md] += 1
  ln = md
  v *= 10
  v %= 2019

d[0] += 1
for i in range(2019):
  ans += d[i]*(d[i]-1)/2 #1~(n-1)までの和

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
Q = int(input())
prime = set()
for i in range(1,100000,2):
    if len(make_divisors(i)) == 2:
        if len(make_divisors((i+1)//2)) == 2:
            prime.add(i)
for i in range(Q):
    l,r = (int(x) for x in input().split())
    lr = set(i for i in range(l,r+1,2))
    print(len(prime & lr))

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
Q = int(input())
prime = set()
cuml = []
count = 0
for i in range(1,100000,2):
    if len(make_divisors(i)) == 2:
        if len(make_divisors((i+1)//2)) == 2:
            prime.add(i)
for i in range(1,100000,2):
    if i in prime:
        count += 1
    cuml.append(count)
for i in range(Q):
    l,r = (int(x) for x in input().split())
    if l > 1:
        print(cuml[(r-1)//2]-cuml[(l-3)//2])
    else:
        print(cuml[(r-1)//2])
### BUGGY CODE ###

from collections import deque
#import sys
import copy
#input = sys.stdin.readline

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]

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

    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    nque = deque()
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

#            for j in range(4):
#                ny = y + dy[j]
#                nx = x + dx[j]
#                if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
#                    a[ny][nx] = True
#                    nque.append((ny, nx))
        
        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

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

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


print(count)
### BUGGY CODE ###

A, B, C, K = map(int, input().split())

for i in range(K):
    A, B, C = B+C, A+C, A+B

if abs(A-B) > 10**18:
    print('Unfair')
else:
    print(A-B)

### FIXED CODE ###

A, B, C, K = map(int, input().split())

if K == 0:
    print(A-B)
    exit()

A, B, C = B+C, C+A, A+B

if abs(A-B) > 10**18:
    print('Unfair')
else:
    if K % 2 == 1:
        print(A-B)
    else:
        print(-(A-B))