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

n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0
for i in range(n):
  a = l[i]
  for j in range(i + 1, n):
    b = l[j]
    bel1 = j #OK
    up1 = n #OUT
    while up1- bel1 > 1:
      mid = (bel1 + up1)//2
      if a + b > l[mid]:
        bel1 = mid
      else:
        up1 = mid
    ans += (bel1-j)
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
 
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(l,l[i] + l[j]) - j - 1
print(ans)
### BUGGY CODE ###

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

sushi = []
for i in range(N):
    x, v = map(int, input().split())
    sushi.append((x, v))

left = [0] * N
left2 = [0] * N
right = [0] * N
right2 = [0] * N

d = 0
d2 = 0
cal = 0
for i in range(N):
    x, v = sushi[i]
    d = x
    d2 = x * 2
    cal += v
    right[i] = cal - d
    right2[i] = cal - d2

d = 0
d2 = 0
cal = 0
for i in reversed(range(N)):
    x, v = sushi[i]
    d = C - x
    d2 = (C - x) * 2
    cal += v
    left[i] = cal - d
    left2[i] = cal - d2

ans = 0
# 左側を全部試す
for i in range(N):
    if i == 0:
        ans = max(ans, left[i])
    else:
        ans = max(ans, left[i] + max(max(right2[:i]), 0))
# 右側を全部試す
for i in range(N):
    if i == N - 1:
        ans = max(ans, right[i])
    else:
        ans = max(ans, right[i] + max(max(left2[i+1:]), 0))

print(ans)

### FIXED CODE ###

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

sushi = []
for i in range(N):
    x, v = map(int, input().split())
    sushi.append((x, v))

left = [0] * N
left2 = [0] * N
right = [0] * N
right2 = [0] * N

d = 0
d2 = 0
cal = 0
for i in range(N):
    x, v = sushi[i]
    d = x
    d2 = x * 2
    cal += v
    if i == 0:
        right[i] = max(cal - d, 0)
        right2[i] = max(cal - d2, 0)
    else:
        right[i] = max(cal - d, right[i-1])
        right2[i] = max(cal - d2, right2[i-1])

d = 0
d2 = 0
cal = 0
for i in reversed(range(N)):
    x, v = sushi[i]
    d = C - x
    d2 = (C - x) * 2
    cal += v
    if i == 0:
        left[i] = max(cal - d, 0)
        left2[i] = max(cal - d2, 0)
    else:
        left[i] = max(cal - d, left[i-1])
        left2[i] = max(cal - d2, left[i-1])

ans = 0
# 左側を全部試す
for i in range(N):
    if i == 0:
        ans = max(ans, left[i])
    else:
        ans = max(ans, left[i] + right2[i-1])
# 右側を全部試す
for i in range(N):
    if i == N - 1:
        ans = max(ans, right[i])
    else:
        ans = max(ans, right[i] + left2[i+1])

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

mod = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split(" ")))

ans = sum((A[i] * A[j]) % mod for i in range(0,N-1) for j in range(i+1,N))

print(ans % mod)


### FIXED CODE ###

mod = 1000000007
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

"""
累積話を計算しておく: O(N)
"""
_sum = 0
for i in range(N):
    _sum += A[i]
    _sum %= mod

"""
1重ループ内で下記を行う: O(N)

- 端のブロックを累積和から崩す（減算）
- 端のブロックと累積和をかける
- modをとる
"""
ans = 0
for i in range(N):
    # 累積和の端のブロックを崩す
    _sum -= A[i]

    ans += A[i] * _sum
    ans %= mod

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

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

i=0
r="YES"

while(i<l):
  j=0
  while(j<l):
    if(i!=j):
      if(list[i]==list[j]):
        r="NO"
    j+=1
  i+=1

print(r)

### FIXED CODE ###

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

def has_duplicates(seq):
    return len(seq) != len(set(seq))

r=has_duplicates(list)

if(str(r)=="False"):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

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

last=[-1]*(2*10**5+1)
nex=[-1]*n
prog=[0]*n

for i,a in enumerate(A*2):
    l=last[a]
    last[a]=i%n
    if nex[l]==-1 and l!=-1:
        nex[l]=(i+1)%n
        if i>=n or i+1==n:
            prog[l]=1
if nex[-1]==0:
    prog[-1]+=1

flag=False #いっぱいループ済か
stage=0
now=0
roop=[-1]*n
while True:
    if roop[now]!=-1 and flag==False:
        flag=True
        rr=stage-roop[now]
        stage=k-1-(k-1-stage)%rr
    if stage+prog[now]==k:
        break
    roop[now]=stage
    stage+=prog[now]
    now=nex[now]

A=A[now:]+A if k-1-stage else A[now:]
check=[0]*(2*10**5+1)
stack=[]
for a in A:
    if check[a]:
        while check[a]:
            check[stack.pop()]=0
        continue
    stack.append(a)
    check[a]=1

print(*stack)

### FIXED CODE ###

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

last=[-1]*(2*10**5+1)
nex=[-1]*n
prog=[0]*n

for i,a in enumerate(A*2):
    l=last[a]
    last[a]=i%n
    if nex[l]==-1 and l!=-1:
        nex[l]=(i+1)%n
        if i>=n or i+1==n:
            prog[l]=1
if nex[-1]==0:
    prog[-1]+=1

flag=False #いっぱいループ済か
stage=0
now=0
roop=[-1]*n
while True:
    if roop[now]!=-1 and flag==False:
        flag=True
        rr=stage-roop[now]
        stage=k-1-(k-1-stage)%rr
    if stage+prog[now]>=k:
        break
    roop[now]=stage
    stage+=prog[now]
    now=nex[now]

A=A[now:]+A if k-1-stage else A[now:]
check=[0]*(2*10**5+1)
stack=[]
for a in A:
    if check[a]:
        while check[a]:
            check[stack.pop()]=0
        continue
    stack.append(a)
    check[a]=1

print(*stack)
### BUGGY CODE ###

import copy

n = int(input())
a = []
a_bak = []
a_sorted = []

for i in range(n):
    a.append(int(input()))

for i in range(n):
    a_bak = copy.copy(a)
    
    a_bak[i] = 0

    a_sorted = sorted(a_bak, reverse=True)

    print(a_sorted[0])

### FIXED CODE ###

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

sorted_a = sorted(a)

max_a = sorted_a[-1]
max_a_r = sorted_a[-2]

for i in range(n):
    if a[i] == max_a:
        print(max_a_r)
    else:
        print(max_a)
### BUGGY CODE ###

def solve():
    ans = 1
    N = int(input())
    s = input()
    ans = 0
    for i in range(1000):
        t = str(i).zfill(3)
        t_index = 0 
        for s_index in range(N):
            if s[s_index] == t[t_index]:
                t_index += 1
                if t_index == 3:
                    break
        if t_index == 3:
            ans += 1
    print(ans)
solve()

### FIXED CODE ###

n = int(input())
s = input()

ans = 0
# 000 ～　999 がsから作成できるか確認していく
for i in range(1000):
    p = str(i).zfill(3)

    s_index_100 = s.find(p[2])
    if s_index_100 == -1:
        continue

    s_index_10 = s.find(p[1], s_index_100+1)
    if s_index_10 == -1:
        continue

    s_index_1 = s.find(p[0], s_index_10+1)
    if s_index_1 == -1:
        continue
    ans += 1

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

n=int(input())
a=list(map(int,input().split()))
mul=1
for i in range(len(a)):
    mul=mul*a[i]
if(mul<1000000000000000001):
    print(mul)
else:
    print(-1)
    

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mul=1
key=0
for i in range(len(a)):
    if a[i]==0:
        key=1
        print(0)
        break;
if key==0:
    for i in range(len(a)):
        mul=mul*a[i]
        if mul>1000000000000000000:
            break
    if(mul<1000000000000000001):
        print(mul)
    else:
        print(-1)
### BUGGY CODE ###

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

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        sup = int(x/F)
        if sup < A:
            syugyo += A-sup
    if syugyo <= k:
        return True
    return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)


### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisection(l,r,f,discrete=True,left=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return h if not discrete else l if left else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    def check(x): # xが必要かどうかを判定する
        dp=[0]*k # k未満が実現できるかだけを判定
        dp[0]=1
        for i in range(n):
            if(i==x): continue
            newdp=dp[:] # i番目を使わない場合
            a=A[i]
            for j in range(k):
                if(j+a<k):
                    newdp[j+a]=max(dp[j+a],dp[j])
            dp=newdp
        return any(dp[i] for i in range(max(0,k-A[x]),k))
    print(bisection(0,n-1,check,left=False))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=[min(a,k+1) for a in A]
    A.sort()
    mask=(1<<k)-1

    def check(i): # i のカードを除いて、k-a[i]<=s<k が作れるか
        if(k-A[i]<0): return True
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])
            dp&=mask

        dp>>=(k-A[i])
        return dp>0

    print(bisection(0,n-1,check,left=False))
resolve()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,u,v=map(int, input().split())
u-=1
v-=1
ab=[list(map(int, input().split())) for _ in range(n-1)]
graph = [[] for _ in range(n+1)]
for a,b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

dist=[[-1, -1] for _ in range(n)]
dist[v][0]=0
dist[u][1]=0

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][0]==-1:
            dist[vvv][0]=dist[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][1]==-1:
            dist[vvv][1]=dist[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
dist.sort(reverse=True)

for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
 
N,u,v = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(N-1)]
E = [[] for _ in range(N+1)]
for a,b in edges:
    E[a].append(b)
    E[b].append(a)
 
depth = [[-1,-1] for _ in range(N+1)] 
depth[v][0] = 0
depth[u][1] = 0

def dfs1(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][0] == -1:
            depth[vvv][0] = depth[v][0] + 1
            dfs1(E,vvv)
 
def dfs2(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][1] == -1:
            depth[vvv][1] = depth[v][1] + 1
            dfs2(E,vvv)
dfs1(E,v)
dfs2(E,u)
depth = sorted(depth, reverse=True)
idx = 0
while True:
    if depth[idx][0] - depth[idx][1] >= 1:
        print(depth[idx][0]-1)
        exit()
    else:
        idx += 1
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
C = []
for i in range(M):
  b, c = map(int, input().split())
  for i in range(b):
    C.append(c)

A.sort()
C.sort(reverse=True)
j = 0
while (j < len(C)) and (A[j] < C[j]):
  j += 1
  
ans = int(sum(C[:j]) + sum(A[j:]))
print(ans)

### FIXED CODE ###

import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    change = [[int(i) for i in input().split()] for _ in range(M)]
    change.sort(key = itemgetter(1), reverse = True)

    ai = 0
    for i in range(M):
        cb, c = change[i]
        if ai >= N or c < A[ai]: break
        for _ in range(cb):
            if ai >= N: break
            if A[ai] <= c:
                A[ai] = c
                ai += 1
            else: break
    print(sum(A))
    return 0

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

def main():
    n = int(input())
    s = input().rstrip()
    dp = [[0]*(i+1) for i in range(n)]
    ans = 0
    for i in range(1, n):
        for j in range(i):
            if s[i] == s[j]:
                dp[i][j] += 1
                if 0 < i and 0 < j:
                    dp[i][j] += dp[i-1][j-1]
                dp[i][j] = i-j if i-j < dp[i][j] else dp[i][j]
                ans = dp[i][j] if dp[i][j] > ans else ans
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

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

n,k=map(int,input().split())
p=list(map(int,input().split()))
import numpy as np
p=np.array(p)
ans=0
for i in range(n-k+1):
  temp=p[i:i+k]
  ans=max(ans,sum(temp))
print((ans+k)/2)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
import numpy as np
p=np.array(p)
temp=p[0:k]
tempsum=sum(temp)
ans=tempsum
for i in range(1,n-k+1):
  tempsum=tempsum-p[i-1]+p[i+k-1]
  ans=max(ans,tempsum)
print((ans+k)/2)
### BUGGY CODE ###

#16D8101023J 久保田凌弥 kubotarouxxx python3

a=int(input())
A=[0]*a
x=0
for i in range(a):
 A[i]=int(input())
 for j in range(1,A[i]):
  if A[i]==2:
    x+=1
    continue
  if j==1:
   continue
  elif (A[i]%j)==0:
   break
  elif j==(A[i]-1):
   x+=1
   
print(x)


### FIXED CODE ###

#16D8101023J 久保田凌弥 kubotarouxxx python3
import math as mh
a=int(input())
A=[0]*a
x=0
for i in range(a):
 A[i]=int(input())
 for j in range(1,A[i]):
  if A[i]==2:
    x+=1
    continue
  if j==1:
   continue
  elif (A[i]%j)==0:
   break
  elif j>=mh.sqrt(A[i]):
   x+=1
   break
print(x)
### BUGGY CODE ###

N = int(input())

s = []
for i in range(N):
    # 比較がしやすいようにソートしたものを追加
    s.append(sorted(input()))

count = 0
for i in range(len(s)):
    for j in range(i + 1, len(s)):
        if s[i] == s[j]:
            count += 1

print(count)


### FIXED CODE ###

N = int(input())

s = ''.join(sorted(input()))
h = {s: 1}
count = 0
for i in range(N - 1):
    # 比較がしやすいようにソートしたものを追加
    s = ''.join(sorted(input()))
    if s in h:
        count += h[s]
        h[s] += 1
    else:
        h[s] = 1

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

# coding: utf-8
# Your code here!

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

s = input()

now = s[0]
tmp = 0

h = []
if s[0]=="0":
    h.append(0)

for i in s:
    if i != now:
        now = i
        h.append(tmp)
        tmp=0
        
    tmp+=1
h.append(tmp)

ans = 0

for i in range(0,max(len(h),len(h)-k),2):
    ans = max(ans,sum(h[i:i+k*2+1]))
    ans = max(ans,sum(h[i+1:i+k*2+1]))

print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import numpy as np

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

s = input()

now = s[0]
tmp = 0

h = []
if s[0]=="0":
    h.append(0)

for i in s:
    if i != now:
        now = i
        h.append(tmp)
        tmp=0
    tmp+=1
h.append(tmp)

h = np.array(h)

ans = 0

for i in range(0,max(len(h),len(h)-k),2):
    ans = max(ans,np.sum(h[i:i+k*2+1]))
    
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
A=[0]
if K!=1:
  for k in range(0,N-K+1):
    On=0
    for l in range(0,K):
      On+=P[k+l]
    A.append(On)
  print((max(A)+K)/2)
elif K==N:
  print((sum(P)+N)/2)
else:
  print((max(P)+1)/2)

### FIXED CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	S=sum(P[0:(K)])
	for k in range(0,N-K):
		S=S-P[k]+P[k+K]
		if T<=S:
			T=S
		else:
			continue
	print((T+K)/2)
### BUGGY CODE ###

n=int(input())
a=[0]*n
a=list(map(int,input().split()))
a=sorted(a)
ans=0
List=[]
ans+=1
flag=0
List.append(a[0])

for i in range(1,n):
    m=len(List)
    for j in range(m):
        if (a[i]==List[-1]):
            if (flag==0):
                ans-=1
            flag=1
            break
        elif (a[i]%List[j]==0):
            flag=0
            break
        elif (a[i]<2*List[j]):
            List.append(a[i])
            flag=0
            ans+=1
            break
        elif(j==m-1):
            List.append(a[i])
            flag=0
            ans+=1
            break
print(ans)

### FIXED CODE ###

n=int(input())
a=[0]*n
a=list(map(int,input().split()))
a=sorted(a)
maxnum=a[-1]
check=[True]*(maxnum+1)
before=0

for x in a:
    if (before==x):
        check[x]=False
        continue
    num=2
    while num*x<=maxnum:
        check[x*num]=False
        num+=1
    before=x

ans=0
for i in a:
    ans+=check[i]
    
print(ans)
### BUGGY CODE ###

from collections import deque

H, W = map(int,input().split())
A = []
X = deque(); Y = deque()
for l in range(H):
    a = list(input())
    addX = [n for n, i in enumerate(a) if i == "#"]
    X.extend(addX); Y.extend([l] * len(addX))
    A.append(a)

cntList = deque()
cntList.extend([0] * len(X))

while X and Y:
    x = X.popleft(); y = Y.popleft(); cnt = cntList.popleft()
    for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= y + dy < H and 0 <= x + dx < W and A[y + dy][x + dx] == ".":
            X.append(x + dx); Y.append(y + dy); cntList.append(cnt + 1)
            A[y + dy][x + dx] = "#"
print(cnt)


### FIXED CODE ###

from collections import deque

H, W = map(int,input().split())
A = [list(input()) for _ in range(H)]
p = deque()
for i, Ai in enumerate(A):
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            p.append([i, j, 0])

while p:
    y, x, cnt = p.popleft()
    for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= y + dy < H and 0 <= x + dx < W and A[y + dy][x + dx] == ".":
            p.append([y + dy, x + dx, cnt + 1])
            A[y + dy][x + dx] = "#"
print(cnt)
### BUGGY CODE ###

from sys import stdin
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

prime_list=[i for i in range(1,10001) if is_prime(i)]
oppai=[False]*10000
for i in range(3, 100001,2):
    if i in prime_list and (i+1)/2 in prime_list:
        oppai[i-1]=True
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=map(int,(input().split()))
    if a==b:
        if a in  prime_list and ((a+1)/2) in  prime_list:
            count+=1
    else:
        aa = sum(oppai[:a-1])
        bb=sum(oppai[:b-1])
        count=bb-aa
    print(count)



### FIXED CODE ###

from sys import stdin
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
prime_list=[i for i in range(2,100000) if is_prime(i)]
oppai=[0]*100000
oppai[1]=0
before=1
for num in prime_list:
    if (num+1)//2 in prime_list:
        oppai[before:num - 2] = [oppai[before]] * (num-1 - before)
        oppai[num-1]=oppai[before]+1
    else:oppai[before:num-1]=[oppai[before]]*(num-before)
    before=num-1
oppai[99991:99999]=[oppai[99990]]*8
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=list(map(int,stdin.readline().strip().split()))
    if a==b:
        bb = (oppai[b - 1])
        aa = (oppai[a - 2])
        count = bb - aa
        print(count)
    else:
        if a>=2:
            bb = oppai[b - 1]
            aa = oppai[a - 2]
            count = bb - aa
            print(count)
        else:
            bb = oppai[b - 1]
            count = bb
            print(count)
### BUGGY CODE ###

import bisect

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

A.sort()
F.sort(reverse=True)

if sum(A) <= K:
    ans = 0
else:
    high = max([A[i] * F[i] for i in range(N)])
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        Ki = K
        able = True
        for i in range(N):
            if A[i] * F[i] > mid:
                Ki -= A[i] - mid // F[i]
                if Ki < 0:
                    able = False
                    break
        if able:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

print(ans)


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

A.sort()
F[::-1].sort()

sum_A = A.sum()
if sum_A <= K:
    ans = 0
else:
    high = (A * F).max()
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        if sum_A - np.minimum(A, mid // F).sum() <= K:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

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

import itertools

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

comb = []
for a, b, c in itertools.product(A, B, C):
    comb.append(sum([a, b, c]))

print(*sorted(comb, reverse=True)[:K], sep='\n')


### FIXED CODE ###

import itertools

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

comb_ab = []
for a, b in itertools.product(A, B):
    comb_ab.append(sum([a, b]))

comb_ab_top = sorted(comb_ab, reverse=True)[:K]

comb_abc = []
for ab, c in itertools.product(comb_ab_top, C):
    comb_abc.append(sum([ab, c]))

ans = sorted(comb_abc, reverse=True)[:K]
print(*ans, sep='\n')
### BUGGY CODE ###

n,x=map(int,input().split())
pos=list(map(int,input().split()))
pos2=[abs(p-x) for p in pos]
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

maxpos= max(pos2)
divs=make_divisor_list(maxpos)[::-1]
for j in divs:
    if all(x%j==0 for x in pos2):
        ans=j
        break
print(ans)

### FIXED CODE ###

n,x=map(int,input().split())
pos=list(map(int,input().split()))
pos2=[abs(p-x) for p in pos]
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)
 
        return divisor_list

if n==1: ans=pos2[0]
else:
    minpos= min(pos2)
    divs=make_divisor_list(minpos)[::-1]
    if divs[0]==1:ans=1
    else:
        for j in divs:
            if all(x%j==0 for x in pos2):
                ans=j
                break
print(ans)