Harryxun/stf_run huggingface dataset:
import math
Q = int(input())

def prime(p):
    for i in range(2, int(math.sqrt(p))+1):
        if p % i == 0:
            return False
    return True

# エラトステネスの篩
data = [1]*10**5
data[0],data[1] = 0,0 #
for j in range(2, 10**5):
    if prime(j) == True:
        for k in range(j*2, 10**5, j):
            data[k] = 0
# 2017 like
for k in range(2,10**5)[::-1]: #
    if data[k] == 1 and k % 2 == 1:
        if data[int((k+1)/2)] == 0:
            data[k] = 0
    else: #
        data[k] = 0 #
# 累積和
t = [0]*10**5
for a in range(10**5-1):
    t[a+1] = t[a] + data[a]

for b in range(Q):
    l, r = map(int, input().split(" "))
    print(t[r+1] - t[l])

### FIXED CODE ###

import math 

def prime(n):
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0
    return 1

#エラトステネスのふるい
MAX =100000
is_prime = [1]*(MAX+1)
is_prime[0] = 0 
is_prime[1] = 0
for i in range(2,MAX+1):
    if prime(i) == 1:
        j = i*2
        while j <= MAX:
            is_prime[j] = 0
            j += i

#２０１７のような数かどうか
a = [0]*(MAX+1)
for i in range(0,MAX):
    if i % 2 == 1:
        if is_prime[i]==1 and is_prime[int((i+1)/2)]==1:
            a[i] = 1

#累積和
s = [0] * (MAX+1)
for i in range(0,MAX):
    s[i+1] = s[i] + a[i]

#クエリ処理
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    r += 1

    print(s[r]-s[l])
x = int(input())
for i in range(100000):
	if x * i % 360 == 0:
        print(i)
	    exit()


### FIXED CODE ###

x = int(input())
for i in range(1, 100000):
  if x * i % 360 == 0:
    print(i)
    exit()
import numpy as np

length = int(input())
As = list(map(int, input().split()))

As.sort()

# indexを数値と紐づけるために+1増やした数にする
check = np.zeros(10**6+1)

answer = 0

# 与えられた数列の小さいものから順にループ
for i in range(length):
    if check[As[i]] == 0:
        # 与えられた数値の倍数すべてに1を立てる
        # checkは0始まりのため、0と倍数要素に1が立つ
        check[::As[i]] = 1
        
        # 同じ数字が複数ある場合はカウントさせない
        if As[i] != As[i + 1]:
            answer = answer + 1

print(answer)

### FIXED CODE ###

import numpy as np

length = int(input())
As = list(map(int, input().split()))

As.sort()

# indexを数値と紐づけるために+1増やした数にする
check = np.zeros(10**6+1)

answer = 0

# 与えられた数列の小さいものから順にループ
for i in range(length):
    if check[As[i]] == 0:
        # 与えられた数値の倍数すべてに1を立てる
        # checkは0始まりのため、0と倍数要素に1が立つ
        check[::As[i]] = 1
        
        # checkリストが0の状態で数列の最後であればanswerへの加算は確定
        # また、同じ数字が複数ある場合はカウントさせない
        if  i == (length - 1) or  As[i] != As[i + 1]:
                answer = answer + 1

print(answer)
N = int(input())
ab = list(list(map(int,input().split())) for i in range(N-1))
c = list(map(int,input().split()))
c.sort(reverse=True)
tree = [[-1]for i in range(N)]
for a,b in ab:
    tree[a-1].append(b)
    tree[b-1].append(a)
def func(l):
    if tree[l-1][0] != -1:
        return
    tree[l-1][0] = c.pop(0)
    for i in tree[l-1][1:]:
        func(i)
func(1)
for i in tree:
    print(i[0],end = " ")

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)

N = int(input())
ab = list(list(map(int,input().split())) for i in range(N-1))
c = list(map(int,input().split()))
c.sort(reverse=True)
print(sum(c)-c[0])
tree = [[-1]for i in range(N)]
for a,b in ab:
    tree[a-1].append(b)
    tree[b-1].append(a)
def func(l):
    if tree[l-1][0] != -1:
        return
    tree[l-1][0] = c.pop(0)
    for i in tree[l-1][1:]:
        func(i)
func(1)
for i in tree:
    print(i[0],end = " ")
N = []
K = []
key_num, tmp = map(int, input().split())
x = 0
while x < key_num:
    a, b = map(int, input().split())
    N.append(a)
    K.append(b)
    x += 1
#print(N, K)
input_data = []
n = 0
for i in N:
    now = 1
    while now <= K[n]:
        input_data.append(i)
        now += 1
    n += 1
#print(input_data)
input_data.sort()
print(input_data[key_num])

### FIXED CODE ###

a, b, c = map(int, input().split())
if a > 100 or a < -100:
 exit()
elif -100 > b or 100 < b:
 exit()
elif -100 > c or 100 < c:
 exit()
if a <= c and c <= b:
 print("Yes")
else:
 print("No")
a=str(S)
b=str(T)
del b[-1:]
if a=b:
  print"yes"
else:
  print"No"

### FIXED CODE ###

s=input()
t=input()
if t[:-1]==s:
  print("Yes")
else:
  print("No")
x=int(input())
y=int(input())

a=x+x+1
b=x+y
c=y+y+1

if a>b:
  if a>c:
    ans=a
else:
  if b>c:
    ans=b
  else:
    ans=c
    
print(ans)

### FIXED CODE ###

coin = list(map(int, input().split()))
a=coin[0]
b=coin[1]

sum1=a+a-1
sum2=a+b
sum3=b+b-1

if sum1<sum2:
    if sum3<sum2:
        ans=sum2
    else:
        ans=sum3
else:
    if sum1>=sum3:
        ans=sum1

print(ans)
import bisect

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

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

a.reverse()
cnt = 0
for i in range(1,n):
    if a[i] + cnt == c[i-1]:
        cnt += 1
    a[i] += cnt
        
INF = 10000000000
dp = [INF] * n

for i in range(n):
    t = bisect.bisect_left(dp,a[i])
    if t != n:
        dp[t] = a[i]

print(bisect.bisect_left(dp,INF))

### FIXED CODE ###

import bisect

INF = 10000000000

n = int(input())
a = [0] * n

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

dp = [INF] * n

for i in range(n):
    dp[bisect.bisect_right(dp,a[i])] = a[i]
    
print(bisect.bisect_left(dp,INF))
N = int(input())
two_list = [1, 2, 4, 8, 16,32,64]
for two in two_list:
  if N > two:
  	if two == 64:
    	print(64)
  else:
    print(two)
    exit()
    

### FIXED CODE ###

N = int(input())
two_list = [1, 2, 4, 8, 16,32,64]
answer = 0
for two in two_list:
  if N >= two:
      answer = two
      if two == 64:
          print("64")
  else:
    print(answer)
    exit()
import numpy as np

h,w=map(int,input().split())
tmp=[]
for i in range(h):
        a=list(input())
        tmp.append(a)
ans1=[]
if(w!=1):
    for i in range(h):
        if(len(set(tmp[i]))==1):
            ans1.append(i)
ans2=[]
tmp=list(map(list,zip(*tmp)))
if(h!=1)
    for i in range(w):
        if(len(set(tmp[i]))==1):
            ans2.append(i)
# print(ans1,ans2)
tmp=list(map(list,zip(*tmp)))
tmp=np.delete(tmp,ans1,axis=0)
tmp=np.delete(tmp,ans2,axis=1)
for i in range(len(tmp)):
    for j in range(len(tmp[0])):
        print(tmp[i][j],end="")
    print()

### FIXED CODE ###

import numpy as np

h,w=map(int,input().split())
tmp=[]
for i in range(h):
        a=list(input())
        tmp.append(a)
ans1=[]
if(w!=1):
    for i in range(h):
        if(len(set(tmp[i]))==1 and tmp[i][0]!="#"):
            ans1.append(i)
ans2=[]
tmp=list(map(list,zip(*tmp)))
if(h!=1):
    for i in range(w):
        if(len(set(tmp[i]))==1 and tmp[i][0]!="#"):
            ans2.append(i)
# print(ans1,ans2)
tmp=list(map(list,zip(*tmp)))
tmp=np.delete(tmp,ans1,axis=0)
tmp=np.delete(tmp,ans2,axis=1)
for i in range(len(tmp)):
    for j in range(len(tmp[0])):
        print(tmp[i][j],end="")
    print()
N,X = [int(i) for i in input().split()]
W = []
W = list(map(int, input().split()))
count = 0
Sum = 0
while Sum <= X:
    Sum += W.pop(0)
    count += 1
print(count)

### FIXED CODE ###

N,X = [int(i) for i in input().split()]
W = []
for j in input().split():
    W.append(j)

count = 1
Sum = 0
while Sum <= X and count < N + 2:
    if count < N + 1:
        Sum += int(W.pop(0))
    count += 1
print(count-1)
while True:
    line = input()
    if line == '':
        break
    a, b = map(int, line.rstrip().split())
    print(len(str(a + b)))



### FIXED CODE ###

while True:
    try:
        a, b = map(int, input().rstrip().split())
        print(len(str(a + b)))
    except Exception:
        break
import fractions
from collections import defaultdict

def lcm(a, b):
    return a * b / fractions.gcd(a, b)

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

d_N = {}

for n in range(N):
    d = fractions.gcd(n, N)
    d_N[(n // d, N // d)] = n

for m in range(M):
    d = fractions.gcd(m, M)
    k = (m // d, M // d)
    if k in d_N:
        if S[d_N[k]] != T[m]:
            print('No')
            exit()

L = int(lcm(N, M))
i = 1
while True:
    flag = True
    L_ = L * i
    a = ['0'] * L_
    for j in range(N):
        a[L_ // N * j] = S[j]
    
    for j in range(M):
        if (a[L_ // M * j] != '0') and (a[L_ // M * j] != T[j]):
            flag = False
            break
        else:
            a[L_ // M * j] = T[j]

    if flag:
        print(L_)
        exit()

    i += 1
            







### FIXED CODE ###

import fractions

def lcm(a, b):
    return a * b / fractions.gcd(a, b)

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

d_N = {}

for n in range(N):
    d = fractions.gcd(n, N)
    d_N[(n // d, N // d)] = n

for m in range(M):
    d = fractions.gcd(m, M)
    k = (m // d, M // d)
    if k in d_N:
        if S[d_N[k]] != T[m]:
            print(-1)
            exit()

L = int(lcm(N, M))
print(L)
N,M = map(int,input().split())


li = ["#"]*N
A = "#"
if N==1:
    s,c = map(int,input().split())
    if not c==A and not c=="#":
        print(-1)
        break
    else:
        A=c
else:   
    if A == "#":
        print(0)
    else:
        print(int(A))
    

for i in range(M):
    s,c = map(int,input().split())
    if s==1 and c==0:
        print(-1)
        break

    if not li[s-1]=="#" and not li[s-1]==c:
        print(-1)
        break
    if li[s-1]=="#":
        li[s-1]=c
    
else:
    if li[0]=="#":
        li[0]=1
        
    num="".join(map(str,li))
    num_new=num.replace("#","0")
    print(num_new)

### FIXED CODE ###

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


li = ["#"]*N
A = "#"
if N==1:
    for i in range(M):
        s,c = map(int,input().split())
        if not c==A and not A=="#":
            print(-1)
            exit()
        else:
            A=c
  
    if A == "#":
        print(0)
    else:
        print(int(A))
    exit()
    

for i in range(M):
    s,c = map(int,input().split())
    if s==1 and c==0:
        print(-1)
        break

    if not li[s-1]=="#" and not li[s-1]==c:
        print(-1)
        break
    if li[s-1]=="#":
        li[s-1]=c
    
else:
    if li[0]=="#":
        li[0]=1
        
    num="".join(map(str,li))
    num_new=num.replace("#","0")
    print(num_new)
import numpy as np

def solve():
    
    n = int(input())
    
    divisors = np.zeros(n+1, np.int64)
    
    for i in range(1, n+1):
        for j in range(i, n+1, i):
            divisors[j] += 1
    #print(divisors)
    
    ans = 0
    for k in range(n+1):
        ans += (k * divisors[k])
    
    print(ans)

from numba import jit

@jit
solve()

### FIXED CODE ###

import numpy as np
from numba import jit

@jit
def solve():
    
    n = int(input())
    
    divisors = np.zeros(n+1, np.int64)
    
    for i in range(1, n+1):
        for j in range(i, n+1, i):
            divisors[j] += 1
    #print(divisors)
    
    ans = 0
    for k in range(n+1):
        ans += (k * divisors[k])
    
    print(ans)

solve()
r,g=map(int,input().split())
print((2*g)-r)

### FIXED CODE ###

r=int(input())
g=int(input())
print((2*g)-r)
a,b=[int(x) for x in input().split()]
if a > b:
 print('a > b')
else if a = b:
 print('a = b')
else:
 print('a < b')


### FIXED CODE ###

a,b=[int(x) for x in input().split()]
if a > b:
 print('a > b')
elif a == b:
 print('a == b')
else:
 print('a < b')
a,b,c,d=map(int,input().split())
if a+b < c+d
    print('Right')
elif a+b > c+d
    print('Left')
else
    print('Balanced')


### FIXED CODE ###

a,b,c,d = map(int,input().split())
if a+b < c+d:
    print('Right')
elif a+b > c+d:
    print('Left')
else:
    print('Balanced')
import sys

compare_counter = 0
array = [0 for x in range(500000)]

def merge(left, mid, right):
    n_fore = mid - left
    n_rear = right - mid
    l_fore = array[left:left + n_fore]
    l_fore.append(sys.maxsize)
    l_rear = array[mid:mid + n_rear]
    l_rear.append(sys.maxsize)

    i = j = 0
    global compare_counter
    compare_counter += (right - left)
    for k in range(left, right):
        if l_fore[i] < l_rear[j]:
            array[k] = l_fore[i]
            i += 1
        else:
            array[k] = l_rear[j]
            j += 1


def merge_sort(left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)
    return


def main():
    start = time.time()
    n = int(input())
    for idx, tmp in enumerate(input().split()):
        array[idx] = int(tmp)

    merge_sort(0, n)

    print(" ".join(map(str, array[:n])))
    print(compare_counter)

    return


main()


### FIXED CODE ###

import sys
#import time

compare_counter = 0
array = [0 for x in range(500000)]

def merge(left, mid, right):
    n_fore = mid - left
    n_rear = right - mid
    l_fore = array[left:left + n_fore]
    l_fore.append(sys.maxsize)
    l_rear = array[mid:mid + n_rear]
    l_rear.append(sys.maxsize)

    #print(left, mid, right)
    i = j = 0
    global compare_counter
    compare_counter += (right - left)
    for k in range(left, right):
        if l_fore[i] < l_rear[j]:
            array[k] = l_fore[i]
            i += 1
        else:
            array[k] = l_rear[j]
            j += 1


def merge_sort(left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)
    return


def main():
    #start = time.time()
    n = int(input())
    for idx, tmp in enumerate(input().split()):
        array[idx] = int(tmp)
    #print("time", time.time()-start)
    merge_sort(0, n)
    #print("time", time.time()-start)
    print(" ".join(map(str, array[:n])))
    print(compare_counter)
    #print("time",time.time()-start)
    return


main()
n = input()
a_list = input().split(" ")

b = [int(a) for a in a_list]
max = 10**9 + 7

sum = 0
for i in range(0, len(b)-2):
  for j in range(i+1, len(b)-1):
    sum += b[i] * b[j]
    while sum => max:
      sum -= max
print(sum)


### FIXED CODE ###

n = input()
 
max = 10**9 + 7
 
a_list = [int(a) % max for a in input().split(" ")]
a_sum = sum(a_list)

total = 0
for i in range(0, len(a_list)-1):
    a_sum -= a_list[i]
    total += a_list[i] * a_sum
total = total % max
print(total)
from collections import deque
H, W = list(map(int, input().split()))

city = []

for _ in range(H):
    city.append(list(input()))

black_grid = []

for i in range(H):
    for j in range(W):
        if city[i][j] == "#":
            black_grid.append((i, j))

dist = [[float("inf") for _ in range(W)] for _ in range(H)]

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

for start in black_grid:
    sx, sy = start
    queue = deque()
    queue.append(start)
    dist[sy][sx] = 0

    while len(queue) > 0:
        now_x, now_y = queue.popleft()

        for dx_, dy_ in zip(dx, dy):
            adj_x = now_x + dx_
            adj_y = now_y + dy_

            if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
                continue

            if city[adj_y][adj_x] == "#":
                continue

            #初めてそのマスに到達する場合
            if dist[adj_y][adj_x] > H*W:
                dist[adj_y][adj_x] = dist[now_y][now_x] + 1
                queue.append((adj_x, adj_y))

            elif dist[adj_y][adj_x] > dist[now_y][now_x] + 1:
                dist[adj_y][adj_x] = dist[now_y][now_x] + 1
                queue.append((adj_x, adj_y))

ans = -1
for i in range(H):
    for j in range(W):
        if dist[i][j] <= H*W:
            ans = max(dist[i][j], ans)


print(ans)


### FIXED CODE ###

from collections import deque
H, W = list(map(int, input().split()))

g = []

for _ in range(H):
    g.append(list(input()))

dist = [[-1 for _ in range(W)] for _ in range(H)]
queue = deque()

for i in range(H):
    for j in range(W):
        if g[i][j] == "#":
            dist[i][j] = 0
            queue.append((j, i))

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

while len(queue) > 0:
    now_x, now_y = queue.popleft()

    for dx_, dy_ in zip(dx, dy):
        adj_x = now_x + dx_
        adj_y = now_y + dy_

        if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
            continue

        if g[adj_y][adj_x] == "#" :
            continue

        if g[adj_y][adj_x] == ".":
            g[adj_y][adj_x] = "#"
            queue.append((adj_x, adj_y))
            dist[adj_y][adj_x] = dist[now_y][now_x] + 1

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(dist[i][j], ans)

print(ans)
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

a, b = li()

print((a+b) // 2 if (a+b) % 2 == 0 else "IMPOSSIBLE"

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

a, b = li()

print((a+b) // 2 if (a+b) % 2 == 0 else "IMPOSSIBLE")
input= input()
print(input * input * input)

### FIXED CODE ###

input = int(input())
print(input ** 3)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    A, B, K = map(int, input().split())

    for i in list(range(A, B + 1)):
        if A - 1 <= i <= A + K - 1 or B + 1 >= i >= B + 1 - K:
            print(i)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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


def main():
    A, B, K = map(int, input().split())
    AK = [i for i in range(A, min(B + 1, A + K))]
    BK = [i for i in range(max(A, B - K + 1), B + 1)]

    result = list(set(AK) | set(BK))
    result.sort()

    for i in result:
        print(i)


if __name__ == "__main__":
    main()
import sys
def main():
    tmp = sys.stdin.readline()
    while tmp:
        tmp = sys.stdin.readline().split("")
        if a > b:
            c = a
            d = b
        else:
            c = b
            d = a

        

        tmp = sys.stdin.readline()

        
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

#最大公約数
def gcd(x, y):
    s = x / y
    r = x % y
    if r == 0:
        return y
    else:
        return gcd(y, r)

#最小公倍数
def lcm(x, y):
    return x*y/gcd(x, y)

def main():
    #print ("a")
    for line in iter(sys.stdin.readline, ""):
        #print (line)
        #tmp = sys.stdin.readline().split(" ")
        #print ("b")
        tmp = line.split(" ")
    
        a = int(tmp[0])
        b = int(tmp[1])
        #print ("a="+str(a))
        #print ("b="+str(b))
        #b = sys.stdin.readline()
        #print ("d")
        if a > b:
            c = a
            d = b
        else:
            c = b
            d = a

        print (str(gcd(c, d)) + " " + str(int(lcm(c,d))))

        #tmp = sys.stdin.readline()
        #if len(tmp) == 1:
        #    break
        #else:
        #    tmp = tmp.split(" ")

    #print ("exit")
     
if __name__ == "__main__":
    main()
# https://atcoder.jp/contests/agc018/tasks/agc018_a

n, k = map(int, input().split())
nums = [int(i) for i in input().split()]
# ボールはどんどん増えていく
nums.sort()
if k <= nums[-1]:
    diff = set([])
    for i in range(1, n):
        diff.add(abs(nums[i] - nums[i - 1]))

    diff = list(diff)
    dp = [False] * (k + 1)
    dp[0] = True
    for num in nums:
        if num <= k:
            dp[num] = True
    for i in range(len(diff)):
        num = nums[i]
        for j in range(k + 1):
            if j - num >= 0:
                dp[j] = dp[j - num] or dp[j]

    if dp[k]:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

# https://atcoder.jp/contests/agc018/tasks/agc018_a

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

def gcd(x, y): #GCD
    # greatest_common_divisor
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

MAX = max(nums)
GCD = nums[0]
for num in nums:
    GCD = gcd(GCD, num)

if k <= MAX and k % GCD == 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
p = 1
B = [-1]*N
B[0] = 0
count = 1
while K < count :
	p = A[p-1]
	if B[p-1] != -1:
		break
	B[p-1] = count
	count += 1
if K < count:
	print(p)
	return
K -= count
K = K % (count-B[p-1])
for i in range(K):
	p = A[p-1]
print(p)

	


### FIXED CODE ###

import sys
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
p = 1
B = [-1]*N
B[0] = 0
count = 1
while K >= count:
	p = A[p-1]
	if B[p-1] != -1:
		break
	B[p-1] = count
	count += 1
if K < count:
	print(p)
	sys.exit()
K -= count
K = K % (count-B[p-1])
for i in range(K):
	p = A[p-1]
print(p)
from math import gcd

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

np = (B - A + 1) + (-(B - A) // C)
nq = (B - A + 1) + (-(B - A) // D)


def coprime(a, b):
    return gcd(a, b) == 1


def lcm(a, b):
    return  (a * b) // gcd(a, b)


if coprime(C, D) == True:
    npq = (B - A + 1) + (-(B - A) // (C * D))
    print(np + nq - npq)
else:
    npq_ = (B - A + 1) + (-(B - A) // lcm(C, D))
    print(np + nq - npq_ - 1)


### FIXED CODE ###

from fractions import gcd

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


def lcm(a, b):
    return  (a * b) // gcd(a, b)


nbc = B - B // C
nbd = B - B // D
nbl = B - B // lcm(C, D)

nac = A - 1 - ((A - 1) // C)
nad = A - 1 - ((A - 1) // D)
nal = A - 1 - ((A - 1) // lcm(C, D))

b = nbc + nbd - nbl
a = nac + nad - nal

print(b - a)
import fractions
N=int(input())
A=list(map(int, input().split()))

MOD=10**9+7

g=A[0]
for i in range(1, N):
    g = g*A[i]//fractions.gcd(g, A[i])
ans=0
for i in range(N):
  ans+=int(g/A[i])%MOD
  ans%=MOD
print(ans)

### FIXED CODE ###

import fractions
N=int(input())
A=list(map(int, input().split()))

MOD=10**9+7

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

g=A[0]
for i in range(1, N):
    g = g*A[i]//fractions.gcd(g, A[i])
ans=0
g%=MOD
for i in range(N):
  ans+=g*modinv(A[i],MOD)
  ans%=MOD
print(ans)
a, b = input()
print('DH'[a==b])

### FIXED CODE ###

a, b = input().split()
print('DH'[a==b])
# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret


N, A, B = map(int, input().split())
MOD = 10**9+7
F = FactMod(N+1, MOD)

print(pow(N, 2, MOD)-1 - F.comb(N, A) - F.comb(N, B))


### FIXED CODE ###

# -*- coding: utf-8 -*-


def comb(N, A):
    x = 1
    for i in range(A):
        x *= N
        N -= 1
        x %= MOD
    y = 1
    for i in range(A):
        y *= A
        A -= 1
        y %= MOD
    return x*pow(y, MOD-2, MOD) % MOD


N, A, B = map(int, input().split())
MOD = 10**9+7
print((pow(2, N, MOD)-1-comb(N, A)-comb(N, B)+MOD) % MOD)
a = list(map(int,input().split()))
print(a + int(b/2))

### FIXED CODE ###

a = list(map(int,input().split()))
print(a[0] + int(a[1]/2))