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

from collections import Counter
from math import sqrt
n = int(input())
a = Counter(map(int, input().split()))
ans = n
for num, count in a.items():
    if count > 1:
        ans -= count
        continue
    if 1 in a and num != 1:
        ans -= count
        continue
    i = 2
    while i <= sqrt(num):
        if num % i == 0:
            if i in a or (num // i) in a:
                ans -= count
                break
        i += 1
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
MAX = 1000000 + 9
dp = [True] * MAX
for num in a:
    for i in range(num*2, MAX, num):
        dp[i] = False
ans = 0
for num in a:
    if dp[num] and a[num] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
 
for i in range(n):
    for j in range(i+1, n+1):
        if (s[i:j] in s[j:]):
            if ans < len(s[i:j]):
                ans = len(s[i:j])
        else:
            break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
high = n//2
low = 1
ans = 0

while low <= high:
    t = set()
    i = (high+low)//2
    for j in range(n-i*2+1):
        t.add(s[j:i+j])
        if s[i+j:j+2*i] in t:
            if ans < i:
                ans = i
                low = i+1
                break
    if ans < i:
        high = i-1
print(ans)
### BUGGY CODE ###

n = int(input())
word_list = [input() for i in range(n)]

def make_charcount(word):
    charcount = {}
    for c in word:
        if c not in charcount:
            charcount[c] = 1
        else:
            charcount[c] += 1
    return charcount

charcount_list = {}
charcount_list_index = 0
same_log = {}
for word in word_list:
    this_charcount = make_charcount(word)
    index = -1
    for i in charcount_list:
        if charcount_list[i] == this_charcount:
            index = i
            break
    if index != -1:
        if index not in same_log:
            same_log[index] = 1
        else:
            same_log[index] += 1
    else:
        charcount_list[charcount_list_index] = this_charcount
        charcount_list_index += 1
        
result = 0
for index in same_log:
    cnt = same_log[index]
    result += int(cnt*(cnt+1)/2)
print(result)

### FIXED CODE ###

n = int(input())

result = 0
word_list = {}

for i in range(n):
    input_word = "".join(sorted(input()))
    flag = 1
    if input_word in word_list:
        word_list[input_word] += 1
        result += word_list[input_word]
        flag = 0
    else:
        word_list[input_word] = 0

print(result)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
colors = [R, G, B]
colors.sort()
ans = 0

for c1 in range(N//colors[2]+1, -1, -1):
    C1 = c1*colors[2] 
    for c2 in range(N//colors[1], -1, -1):
        C2 = c2*colors[1] 
        C3 = (N-C1-C2)/colors[0]
        if C3 >= 0 and C3.is_integer():
            ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
r, g, b = 0, 0, 0
ans = 0
 
for r in range(N//R+1):
    Rr = R*r
    for g in range(N//G+1):
        Gg = G*g
        Bb = N-Rr-Gg

        if Bb < 0:
            break
        if Bb%B == 0:
            ans += 1
 
print(ans)
### BUGGY CODE ###

from math import factorial

MOD = 10 ** 9 + 7

def mult(a, b):
  return ((a % MOD) * (b % MOD)) % MOD

def solve():
  N = int(input())
  S = list(map(lambda c: c == 'W', input())) # W: True, B: False
  if S[0] or S[2 * N - 1]: return 0

  D = [ True ] * (2 * N) # L: True, R: False
  d = True
  for i in range(1, N * 2):
    if S[i] == S[i - 1]: d = not d
    D[i] = d

  C = 1
  c = 0
  for d in D:
    if d: c += 1
    else:
      C *= c
      c -= 1
      if c < 0: return 0

  return mult(factorial(N), C) if c == 0 else 0

print(solve())

### FIXED CODE ###

MOD = 10 ** 9 + 7

def solve():
  N = int(input())
  S = [s == 'W' for s in input()] # W: True, B: False
  if S[0] or S[2 * N - 1]: return 0

  ans = 1
  cnt = 1
  d = True # L: True, R: False
  for i in range(1, N * 2):
    if S[i] == S[i - 1]: d = not d
    if d: cnt += 1
    else:
      ans = (ans * cnt) % MOD
      cnt -= 1

  for i in range(1, N + 1): ans = (ans * i) % MOD

  return ans if cnt == 0 else 0

print(solve())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
dd = defaultdict(list)
count = 0
for i in range(N - 1):
    if dd[i + A[i]] == []:
        for j in range(i + 1, N):
            if j - A[j] == i + A[i]:
                dd[i + A[i]].append(j)
                count += 1
    else:
        for j in dd[i + A[i]]:
            if j > i:
                count += 1
print(count)

### FIXED CODE ###

import sys


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * (10 ** 6)
    ans = 0
    for i in range(n):
        if i - a[i] > 0:
            ans += b[i - a[i]]
        if i + a[i] < 10 ** 6:
            b[i + a[i]] += 1
    print(ans)


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

#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
#mod = 10**9 + 7

mod=998244353


n,m,k=MI()
beki=[0 for i in range(n)]
beki[0]=m%mod
for i in range(n-1):
    beki[i+1]=(beki[i]*(m-1))%mod
    
def cmod(n, r, p):
    x,y  = 1, 1
    for i in range(r):
        x = x * (n - i) % p
        y = y * (r - i) % p
    return (x * pow(y, p - 2, p)) % p
ans=0

for i in range(k+1):
    j=n-i-1
    ans+=(beki[j]*cmod(n-1,i,mod))%mod
    #print(beki[j]*cmod(n-1,i,mod))
print(ans%mod)

### FIXED CODE ###

#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
#mod = 10**9 + 7
mod=998244353
x=220000
fact=[0 for i in range(x)]
invfact=[0 for i in range(x)]
fact[0]=1

def cmod(n,k,mod):
    if n<0 or n<k:
        return 0
    return (fact[n]*invfact[n-k]*invfact[k])%mod
for i in range(1,x):
    fact[i]=(fact[i-1]*i)%mod
#print(fact)
invfact[-1]=pow(fact[-1],mod-2,mod)
#print(invfact)
for j in range(x-1,0,-1):
    #print(j)
    invfact[j-1]=(invfact[j]*(j))%mod
#print(invfact)

n,m,k=MI()
beki=[0 for i in range(n)]
beki[0]=m%mod
for i in range(n-1):
    beki[i+1]=(beki[i]*(m-1))%mod
    
ans=0

for i in range(k+1):
    j=n-i-1
    ans+=(beki[j]*cmod(n-1,i,mod))%mod
    #print(beki[j]*cmod(n-1,i,mod))
print(ans%mod)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
ans=["No"]*n
for i in range(n):
    if a.count(i+1)>q-k:
        ans[i]="Yes"
for i in range(n):
    print(ans[i])

### FIXED CODE ###

from collections import Counter
n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
c=Counter(a)
ans=["No"]*n
for i in range(n):
    if c[i+1]>q-k:
        ans[i]="Yes"
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])*l[k][2]
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            xcal[i][j] *= l[j][2]
            ycal[i][j] *= l[j][2]
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])
                if cost > ans[count]:
                    break
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
calc = 0
for i in range(n):
    calc += ((sum(a[i+1:]) % 1000000007) * a[i]) % 1000000007
calc %= 1000000007
print(calc)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sum_a = sum(a)
calc = 0
for i in range(n):
    sum_a -= a[i]
    calc += ((sum_a % 1000000007) * a[i]) % 1000000007
calc %= 1000000007
print(calc)
### BUGGY CODE ###

s = input()
k = int(input())

a = list()

for i in range(1,27):
    b = set()
    for j in range(len(s)):
        if(ord(s[j])==(i+96)):
            for m in range(j,len(s)):
                #print(s[j:m+1])
                b.add(s[j:m+1])
    a.append(list(b))

for i in range(26):
    a[i].sort()
    
cn = 0
for i in range(26):
    if(len(a[i])+cn>=k):
        for j in range(len(a[i])):
            cn += 1
            if(cn == k):
                print(a[i][j])
    else:
        cn += len(a[i])
        
#print(a)

### FIXED CODE ###

s = input()
k = int(input())

a = list()

ch = 0
cn = 0
for i in range(1,27):
    b = set()
    for j in range(len(s)):
        if(ord(s[j])==(i+96)):
            for m in range(j,j+k):
                #print(s[j:m+1])
                b.add(s[j:m+1])
                cn += 1
                

    a.append(list(b))
    

for i in range(26):
    a[i].sort()
    
cn = 0
for i in range(26):
    if(len(a[i])+cn>=k):
        for j in range(len(a[i])):
            cn += 1
            if(cn == k):
                print(a[i][j])
    else:
        cn += len(a[i])
        
#print(a)
### BUGGY CODE ###

n, k = map(int, input().split())
l = [int(input()) for _ in range(n)]

from itertools import combinations
x = list(combinations(l, k))

y = []
for i in range(len(x)):
    y.append(max(x[i]) - min(x[i]))

print(min(y))


### FIXED CODE ###

n, k = map(int, input().split())
l = [int(input()) for _ in range(n)]
l = sorted(l)
#print(l)
x = []
for i in range(n-k+1):
    x.append(l[i+k-1] - l[i])
x  = sorted(x)
#print(x)

print(min(x[:k-1]))
### BUGGY CODE ###

X = int(input())


def cal(x, c1, c2, c3, c4, c5):
    if x == 0 or x % 100 == 0:
        print(1)
        exit()

    else:
        now = x - 100
        if now >= 0:
            cal(now-1, c1+1, c2, c3, c4, c5)
            cal(now-2, c1, c2+1, c3, c4, c5)
            cal(now-3, c1, c2, c3+1, c4, c5)
            cal(now-4, c1, c2, c3, c4+1, c5)
            cal(now-5, c1, c2, c3, c4, c5+1)

    return 0


if X >= 2000:
    print(1)
else:
    print(cal(X, 0, 0, 0, 0, 0))


### FIXED CODE ###

X = int(input())
for c in range(X//100 + 1):
    if 100*c <= X and X <= 105*c:
        print(1)
        exit()

print(0)
### BUGGY CODE ###

def resolve():
    N, A = list(map(int, input().split()))
    X = sorted(list(map(int, input().split())))
    cnt = 0
    for bits in range(1, 1<<N):
        flags = list(bin(bits)[2:].zfill(N))
        _X = [x for i, x in enumerate(X) if flags[i]=="1"]
        cnt += 1 if sum(_X)/len(_X) == A else 0
    print(cnt)
    


if '__main__' == __name__:
    resolve()



### FIXED CODE ###

def resolve():
    N, A = list(map(int, input().split()))
    X = [int(i) - A for i in input().split()]
    d = {0: 1}
    for x in X:
        for _sum, count in list(d.items()):
            d[_sum+x] = d.get(_sum+x, 0) + count

    print(d[0]-1)
    


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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict
from itertools import combinations

N = int(input())
H = defaultdict(list)

for i in range(N):
    s = "".join(sorted(input()))
    H[s].append(i)

ret = 0
for v in H.values():
    ret += len(list(combinations(v, 2)))
print(ret)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict
import math

N = int(input())
H = defaultdict(int)

for i in range(N):
    s = "".join(sorted(input()))
    H[s] += 1

ret = 0
for v in H.values():
    if v >= 2:
        ret += math.factorial(v) // (math.factorial(v - 2) * math.factorial(2))
print(ret)
### BUGGY CODE ###

n = input()
array = []
for i in range(n):
	inst = raw_input().split()
	if inst[0] == "insert":
		array.insert(0,inst[1])
	if inst[0] == "delete":
		if inst[1] in array:
			array.remove(inst[1])
	if inst[0] == "deleteFirst":
		array.pop(0)
	if inst[0] == "deleteLast":
		array.pop(len(array)-1)
print " ".join(i for i in array)

### FIXED CODE ###

n = input()
array = []
base = 0
for i in xrange(n):
    inst = raw_input().split()
    if inst[0][0] == 'i':
        array.append(int(inst[1]))
    elif inst[0] == "delete":
        if int(inst[1]) in array:
            x = array[::-1].index(int(inst[1]))
            if x != -1 and int(inst[1]):
                del array[-x-1]
    elif inst[0][6] == 'F':
        array.pop()
    else:
        base += 1
print (" ".join(map(str,array[base:][::-1])))
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
#a=min(s.count("R"),s.count("G"),s.count("B"))
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if s[j]!=s[i] and s[i]!=s[k] and s[j]!=s[k] and j-i!=k-j:
                ans = ans+1
print(ans)

### FIXED CODE ###

n=int(input())
s=list(input())
a=s.count("R")
b=s.count("G")
c=s.count("B")
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    k=2*j-i
    if n-1>=k and (s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]): 
      ans=ans+1
print(a*b*c-ans)
### BUGGY CODE ###

from bisect import bisect_left
def main():
    h, w, m = map(int, input().split())
    bombs = set()
    cnt_row, cnt_col = [0]*(h+1), [0]*(w+1)
    for _ in range(m):
        y, x = map(int, input().split())
        cnt_row[y] += 1
        cnt_col[x] += 1
        bombs.add((y, x))
    ans = 0
    for y, x in bombs:
        ans = max(ans, cnt_row[y]+cnt_col[x]-1)
    col_indexs = [i for i in range(w+1)]
    col_indexs.sort(key=lambda x: cnt_col[x])
    cnt_col.sort()
    for i, row_val in enumerate(cnt_row):
        p = ans - row_val
        idx = bisect_left(cnt_col, p)
        for k in range(idx, w+1):
            j = col_indexs[k]
            if (i, j) in bombs:
                continue
            if ans < row_val + cnt_col[k]:
                ans = row_val + cnt_col[k]
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import bisect_left
def main():
    h, w, m = map(int, input().split())
    bombs = set()
    cnt_row, cnt_col = [0]*(h+1), [0]*(w+1)
    for _ in range(m):
        y, x = map(int, input().split())
        cnt_row[y] += 1
        cnt_col[x] += 1
        bombs.add((y, x))
    max_cnt_row = max(cnt_row)
    max_cnt_col = max(cnt_col)
    idx_row = []
    idx_col = []
    for i in range(h+1):
        if cnt_row[i] == max_cnt_row:
            idx_row.append(i)
    for j in range(w+1):
        if cnt_col[j] == max_cnt_col:
            idx_col.append(j)
    ans = max_cnt_row + max_cnt_col - 1
    for i in idx_row:
        for j in idx_col:
            if not (i, j) in bombs:
                ans = max_cnt_row + max_cnt_col
                break
    print(ans)

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

n = int(input())
li = list(map(int,input().split()))
ans = 0
lgcd = [li[0]]
rgcd = [li[-1]]

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

for i in range(n-1):
    lgcd.append(gcd(lgcd[-1],li[i+1]))
    rgcd.insert(0,gcd(rgcd[0],li[-(i+2)]))

gcd_list = [gcd(lgcd[i],rgcd[i+2]) for i in range(n-2)]

gcd_list.append(lgcd[-2])
gcd_list.append(rgcd[1])

print(max(gcd_list))


### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
lgcd = [0]*n
rgcd = [0]*n
lgcd[0] = li[0]
rgcd[-1] = li[-1]

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

for i in range(n-1):
    lgcd[i+1] = gcd(lgcd[i],li[i+1])
    rgcd[-i-2] = gcd(rgcd[-i-1],li[-(i+2)])

gcd_list = [gcd(lgcd[i],rgcd[i+2]) for i in range(n-2)]

gcd_list.append(lgcd[-2])
gcd_list.append(rgcd[1])

print(max(gcd_list))
### BUGGY CODE ###


import math




N=int(input())

anslist=[]
for i in range(1,N+1):
    ans=0
    if i<=5:
        anslist.append(ans)
    else:
        ma=int(math.sqrt(i))
        mi=max(1,int(math.sqrt(i)/6))
        for x in range(mi,ma):
            for y in range(x,ma):
                for z in range(y,ma):
                    if x**2+y**2+z**2+x*y+y*z+z*x>i:
                        continue
                    if x**2+y**2+z**2+x*y+y*z+z*x==i:
                        if x==y and y==z:
                            ans+=1
                        elif x==y or y==z or z==x:
                            ans+=3
                        else:
                            ans+=6
        anslist.append(ans)
            

for i in range(N):
    print(anslist[i])

### FIXED CODE ###

import math




N=int(input())

anslist=[0]*(N+1)
ma=int(math.sqrt(N))+1
for x in range(1,ma):
    for y in range(x,ma):
        for z in range(y,ma):
            n=x**2+y**2+z**2+x*y+y*z+z*x
            if n <=N:
                if x==y and y==z:
                    anslist[n]+=1
                elif x==y or y==z or z==x:
                    anslist[n]+=3
                else:
                    anslist[n]+=6

            
for i in range(1,N+1):
    print(anslist[i])
### BUGGY CODE ###

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

cnt = 0
for i in a:
    tmp = a.count(i) + a.count(i + 1) + a.count(i - 1)
    if cnt <= tmp:
        cnt = tmp

print(cnt)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)

for key in a:
    d[key] += 1

cnt = 0
for i in d:
    d1 = 0
    d2 = 0
    if (i - 1) in d:
        d1 = d[i - 1]
    if (i + 1) in d:
        d2 = d[i + 1]

    cnt = max(cnt, d[i] + d1 + d2)

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

N, M = map(int,input().split())

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

def waribiki(X,Y):
    return X//(2**Y)

if len(A)==1:
    while M>0:
        A[0] = waribiki(A[0],1)
        M -= 1
else:
    while M>0:
        A.sort(reverse=True)
        m=1
        while M>0 and waribiki(A[0],m)>A[1]:
            m+=1
        A[0] = waribiki(A[0],m)
        M -= m
       

print(sum(A))


### FIXED CODE ###

N, M = map(int,input().split())

def intm(x):
    return int(x)*-1
A = list(map(intm, input().split()))

import heapq

heapq.heapify(A)
while M>0:
    a = -heapq.heappop(A) // 2
    heapq.heappush(A,-a)
    M -= 1
   

print(-sum(A))
### BUGGY CODE ###

import itertools

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

C = list(itertools.combinations(L, 3))

count = 0
for a,b,c in C:
    if a < b + c and b < c + a and c < b + a:
        count += 1 
    
print(count)

### FIXED CODE ###

"""
素直に実装するとN**9
"""

import bisect
 
N = int(input())
L = list(map(int, input().split()))
 
L.sort()
ans = 0
for ai in range(N):
    for bi in range(ai+1, N):
        ci = bisect.bisect_left(L, L[ai]+L[bi])
        if ci > bi:
            ans += ci - bi - 1
        else:
            pass
 
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
f=0
ijk = list()
for i in range(N):
    for j in range(N):
        for k in range(N):
            if(i<j<k):
                if(S[i]==S[j]):
                    pass
                elif(S[i]==S[k]):
                    pass
                elif(S[j]==S[k]):
                    pass
                else:
                    ijk.append([i+1,j+1,k+1])
# print(ijk)
for i in range(len(ijk)):
    if(ijk[i][1]-ijk[i][0] == ijk[i][2]-ijk[i][1]):
        pass
    else:
        f += 1
print(f)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in s:
  if i=="R":r+=1
  elif i=="G":g+=1
  else:b+=1

ans=r*g*b
for i in range(n):
  for j in range(i+1,n):
    k_ = j+(j-i)
    if(k_ >=n):
      break
    ans -= int(s[i]!= s[j] and s[i] != s[k_] and s[j] != s[k_])

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

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(H)]

def find(x):
    for i in range(H):
        for j in range(W):
            if A[i][j]==x:
                return i,j

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    cost=0
    x,y=find(L)
    for j in range(L+D,R+D,D):
        new_x,new_y=find(j)
        cost+=abs(x-new_x)+abs(y-new_y)
        x,y=new_x,new_y
    print(cost)

### FIXED CODE ###

from collections import defaultdict

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(H)]
M=defaultdict(list)
for h in range(H):
    for w in range(W):
        M[A[h][w]]=[h,w]

P=defaultdict(list)
for d in range(1,D+1):
    a=d
    while a+D<=H*W:
        p=abs(M[a][0]-M[a+D][0])+abs(M[a][1]-M[a+D][1])
        if P[d]:
            P[d].append(P[d][-1]+p)
        else:
            P[d]=[0,p]
        a+=D

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    d=L%D
    l=L//D
    r=R//D
    if d==0:
        d=D
        if len(P[d])>0:
            print(P[d][r-1]-P[d][l-1])
        else:
            print(0)
    else:
        if len(P[d])>0:
            print(P[d][r]-P[d][l])
        else:
            print(0)