Harryxun/stf_run huggingface dataset:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

from math import factorial
def cmb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)


def main():
    n=int(input())
    l=[cmb(i,2) for i in Counter(["".join(sorted(input()))for i in range(n)]).values()]
    print(sum(l))
                    
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

from math import factorial
def cmb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)


def main():
    n=int(input())
    l=[cmb(i,2) for i in Counter(["".join(sorted(input()))for i in range(n)]).values() if i>1]
    print(sum(l))
                    
        
if __name__ == '__main__':
    main()
# coding: utf-8

weather = input("Today's weather:")
if weather == "Sunny":
    print("Cloudy")
elif wether == "Cloudy":
    print("Rainy")
elif wether == "Rainy":
    print("Sunny")


### FIXED CODE ###

# coding: utf-8

weather = input()
if weather == "Sunny":
    print("Cloudy")
elif weather == "Cloudy":
    print("Rainy")
elif weather == "Rainy":
    print("Sunny")
while True:
    n = int(raw_input())
    if n == 0:
        break
    m = int(raw_input())-1
    x = int(raw_input())-1
    d = int(raw_input())
    amida = []
    for i in range(d):
        amida.append(map(int, raw_input()))
    rroot = []
    for i in range(d-1,-1,-1):
        if x > 0:
            if amida[i][x-1] == 1:
                x -= 1
        if x < n-1:
            if amida[i][x] == 1:
                x += 1
        rroot.append(x)
    if m == x:
        print 0
    else:
        root = []
        for i in range(d):
            if m > 0:
                if amida[i][m-1] == 1:
                    m -= 1
            if m < n-1:
                if amida[i][m] == 1:
                    m += 1
            root.append(m)
        rroot.reverse()
        for i in range(d):
            if abs(root[i]-rroot[i]) == 1:
                p = min(root[i],rroot[i])
                if p == 0:
                    if amida[i][p+1] == 0:
                        print i+1, p+1
                        break
                elif p == n-1:
                    if amida[i][p-1] == 0:
                        print i+1, p+1
                        break
                else:
                    if amida[i][p-1] + amida[i][p+1]) == 0:
                        print i+1, p+1
                        break
            if i == d-1:
                print 1

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    m,x,d = int(raw_input()),int(raw_input()),int(raw_input())
    amida = ["" for i in range(d)]
    for i in range(d):
        amida[i] = "0" + raw_input() + "0"
    rroot = []
    for i in range(d-1,-1,-1):
        if amida[i][x-1] == "1": x -= 1
        elif amida[i][x] == "1" : x += 1
        rroot.append(x)

    if m == x: print 0
    else:
        root = []
        for i in range(d):
            if amida[i][m-1] == "1": m -= 1
            elif amida[i][m] == "1" : m += 1
            root.append(m)
        rroot.reverse()
        for i in range(d):
            if abs(root[i]-rroot[i]) == 1:
                p = min(root[i],rroot[i])
                if int(amida[i][p-1]) + int(amida[i][p+1]) == 0:
                    print i+1, p
                    break
            if i == d-1: print 1
s,w = map(int,input().split())
if s>w:
  print('safe')
 else:
  print('unsafe')

### FIXED CODE ###

s,w = map(int,input().split())
if s>w:
  print('safe')
else:
  print('unsafe')
import math

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

if N == 2:
  print(max(A))
else:
  G = math.gcd(A[0], A[1])
  H = math.gcd(A[1], A[2])
  I = math.gcd(A[2], A[0])

  print(max(G, H, I))

### FIXED CODE ###


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


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

if N == 2:
  print(max(A))
else:

  L = [0 for j in range(N+1)]
  R = [0 for j in range(N+1)]
  
  for j in range(N):
    L[j+1] = gcd(L[j], A[j])
  for j in reversed(range(N)):
    R[j] = gcd(R[j+1], A[j])

    m = -1
  for j in range(N):
    m = max(m, gcd(L[j], R[j+1]))
  print(m)
from b import resolve
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """41 2
5 6"""
        output = """30"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """10 2
5 6"""
        output = """-1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """11 2
5 6"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """314 15
9 26 5 35 8 9 79 3 23 8 46 2 6 43 3"""
        output = """9"""
        self.assertIO(input, output)
    def test_Sample_Input_1(self):
        input = """41 2
5 6"""
        output = """30"""
        self.assertIO(input, output)
    def test_Sample_Input_2(self):
        input = """10 2
5 6"""
        output = """-1"""
        self.assertIO(input, output)
    def test_Sample_Input_3(self):
        input = """11 2
5 6"""
        output = """0"""
        self.assertIO(input, output)
    def test_Sample_Input_4(self):
        input = """314 15
9 26 5 35 8 9 79 3 23 8 46 2 6 43 3"""
        output = """9"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    s = sum(A)
    if s<=N:
        print(N-s)
    else:
        print(-1)

if __name__ == '__main__':
    resolve()
x=int(input())
from sympy import nextprime
print(nextprime(x))

### FIXED CODE ###

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

x=int(input())
while True:
  if is_prime(x)==True:
    break
  x+=1
print(x)
import sys
import math

read = sys.stdin.read
readline = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    S = int(input())
    x1 = math.ceil(S**0.5)
    x2 = X1**2 -S
    print(0, 0, x1, 1, x2, x1)




if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math

read = sys.stdin.read
readline = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    S = int(input())
    x1 = math.ceil(S ** 0.5)
    x2 = x1 ** 2 - S
    print(0, 0, x1, 1, x2, x1)


if __name__ == '__main__':
    main()
def search(M, l, walkable):
    i, j = (l.pop(0))
    nexts = []
    if i !=0:
        nexts.append((i-1, j))
    if i != len(M)-1:
        nexts.append((i+1, j))
    if j != 0:
        nexts.append((i, j-1))
    if j != len(M[0])-1:
        nexts.append((i, j+1))

    for nex in nexts:
        x, y = nex
        if M[x][y] == '.' and not nex in walkable:
            l.append(nex)
            walkable.append(nex)

inp = ''
while '0 0' != (inp = input().rstrip()):
    i, j = [int(x) for x in inp.split()]
    M = [input() for k in range(j)]
    l = []
    for n in range(j):
        if '@' in M[n]:
            l.append((n, M[n].find('@')))

    walkable = []
    while l:
        search(M, l, walkable)
    print(len(walkable)+1)

### FIXED CODE ###

import queue

def solve(w, h):
    q = queue.Queue()
    m = [['#' for i in range(w+2)] for j in range(h+2)]
    for i in range(h):
        inp = input()
        for j in range(w):
            m[i+1][j+1] = inp[j]
            if m[i+1][j+1] == '@':
                start = [i+1,j+1]
    q.put(start)
    c = 1
    while not q.empty():
        cur = q.get()
        XY = [(1,0), (-1, 0), (0, 1), (0, -1)]
        for x, y in XY:
            cx = cur[0]+x
            cy = cur[1]+y
            if m[cx][cy] == '.':
                m[cx][cy] = '#'
                q.put([cx, cy])
                c+=1
    return c

while True:
    w, h = [int(i) for i in input().split()]
    if w == 0 and h == 0:
        break
    print(solve(w,h))
print(int(input())-int(input())+1)

### FIXED CODE ###

print((lambda a:a[0]-a[1]+1)(list(map(int,input().split()))))
from collections import Counter

N = int(input())
list_s = []
for i in range(N):
    S = input()
    list_s.append(S)

D = Counter(list_s)

print("AC x " + str(D["AC"]))
print("WA x " + str(D["WA"]))
print("TLE x " + str(D["TLE"]))
print("RE x " + str(D["RE"]))


### FIXED CODE ###

N = int(input())

if N%1000 == 0:
  n = N//1000
else:
  n = N//1000 + 1

ans = 1000*n - N
print(ans)
n,a,b=map(int,input().split())

print(n//(a+b)*a+mi,min(a,n%(a+b))
    


### FIXED CODE ###

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

print(n//(a+b)*a+min(a,n%(a+b)))
A, B, C, K = list(map(int, input().split()))

if( A + B >= K ):
    if(A >= K):
        print(K)
    else:
        print(A)
else:
    print(+1*A -1*(K-(A+B)))


### FIXED CODE ###

S = input()
T = input()

flag = True

for i in range(len(S)):
    if(S[i] != T[i]):
        flag = False

if(flag):
    print('Yes')
else:
    print('No')
a = [int(input()) for _ in range(5)]
k = int(input())
m = 0
for ai in a:
  for aj in a:    
    if m < abs(ai - aj):
      m = abs(ai - aj)
if m <= k:
  print('Yay!'')
else:
  print(':(')

### FIXED CODE ###

a = [int(input()) for _ in range(5)]
k = int(input())
m = 0
for ai in a:
  for aj in a:    
    if m < abs(ai - aj):
      m = abs(ai - aj)
if m <= k:
  print('Yay!')
else:
  print(':(')
# -*- coding: utf-8 -*-

def qui(l):
    num = len(l)
    if num == 1: return l
    piv = 0
    piv2 = len(l)-1
    piv3 = int(len(l)/2)
    if l[piv] > l[piv2] > l[piv3]:
        piv = piv2
    elif l[piv] > l[piv3] > l[piv2]:
        piv = piv3
    mini = []
    maxi = []

    for i in range(0,len(l)):
        if i == piv:
            continue
        if l[piv] > l[i]:
            mini.append(l[i])
        elif l[piv] <= l[i]:
            maxi.append(l[i])
    return qui(mini) + [l[piv]] + qui(maxi)

input()
list1 = list(map(lambda x: int(x), input().split(" ")))
result = qui(list1)

print(' '.join(map(str, result)))

### FIXED CODE ###

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

import random
def qui(l):
    num = len(l)
    if num <= 1:
        return l
    piv = random.randrange(0,len(l))
    piv2 = random.randrange(0,len(l))
    piv3 = random.randrange(0,len(l))
    if (l[piv] > l[piv2]) and (l[piv2] > l[piv3]):
        piv = piv2
    elif (l[piv] > l[piv3]) and (l[piv3] > l[piv2]):
        piv = piv3
    elif (l[piv] < l[piv2]) and (l[piv2] < l[piv3]):
        piv = piv2
    elif (l[piv] < l[piv3]) and (l[piv3] < l[piv2]):
        piv = piv3
    else:
        pass
    mini = []
    middlei = []
    maxi = []

    for i in range(0,len(l)):
        if l[i] == l[piv]:
            middlei.append(l[i])
        elif l[piv] > l[i]:
            mini.append(l[i])
        elif l[piv] <= l[i]:
            maxi.append(l[i])
    mini = qui(mini)
    maxi = qui(maxi)
    return mini+ middlei+maxi
input()
list1 = input().split(" ")
for i in range(0, len(list1)):
    list1[i] = int(list1[i])

result = qui(list1)

print(' '.join(map(str, result)))
n,x = (int(i) for i in input().split())  
l = [int(i) for i in input().split()] 
d = 0
i=0
while d <= x:
   d+=l[i]
   i+=1 

print(i) 

### FIXED CODE ###

n,x = (int(i) for i in input().split())  
l = [int(i) for i in input().split()] 
d = 0
i=0
while d <= x:
    try:
        d+=l[i]
    except:
        i+=1
        break
    i+=1

print(i)
import math
a,b=map(int,input().split())
print(1+math,ceil((b-a)/(a-1)))

### FIXED CODE ###

import math
a,b=map(int,input().split())
print(1+math.ceil((b-a)/(a-1)))
import math

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

ans = 0
MOD = 10**9 + 7

factorial = math.factorial(n-1)

p = [0]*(n-1)
p[0] = 1 * factorial%MOD

for i in range(1,n-1):
    p[i] = p[i-1] + (factorial/(i+1))%MOD
    p[i] %= MOD

for i in range(n-1):
    ans += (x[i+1]-x[i])*p[i]
    ans %= MOD

ans %= MOD

print(int(ans))

### FIXED CODE ###

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


def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod

ans = 0
MOD = 10**9 + 7

factorial = 1
for i in range(2,n):
    factorial = (factorial * i%MOD) %MOD

p = [0]*(n-1)
p[0] = 1 * factorial%MOD

for i in range(1,n-1):
    p[i] = p[i-1] + factorial*mod_inv(i+1,MOD)
    p[i] %= MOD

for i in range(n-1):
    ans += (x[i+1]-x[i])%MOD*p[i]
    ans %= MOD

print(int(ans))
a = input()
for i in range(a):
  if a[i] == 1:
    a[i] = 9
  else:
    a[i] = 1
print(a)

### FIXED CODE ###

a = input()
b= ""
for i in range(len(a)):
  if a[i] == "1":
    b += "9"
  else:
    b += "1"
print(b)
K, S = map(int, input().split())
count = 0
if K*3 < S:
    print(count)
else:
    for i in range(K, -1, -1):
        X = i
        YZ = S - X
        for j in range(K, -1, -1):
            Y = j
            Z = YZ - Y
            if Z > K:
                continue
            elif Z < 0:
                continue
            else:
                count += 1
                #print(X,Y,Z)
print(count)

### FIXED CODE ###

S = list(map(str, input().split(",")))
ans = ""
for i in S:
    ans += i + " "
print(ans)
a, b, c = map(int, input().split())
for i in range(a, b):
    if i % c == 0:
        result += str(c)+" "
print(result)

### FIXED CODE ###

a, b, c = map(int, input().split())
result = 0
for i in range(a, b+1):
    if c % i == 0:
        result += 1
print(result)
k = int(input())
x = int(input())
if k * 500 >= x:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

k, x = (int(i) for i in input().split())
if k * 500 >= x:
    print("Yes")
else:
    print("No")
n = int(input())
h = [int(i) for i in input().split()]
for j in range(n-1):
  if h[j] - h[j+1] < -1:
    print("No")
    exit()
  else:
    continue
for k in range(n-2):
  if  h[k] < h[k+1] and h[k+1] < h[k+2]:
     print("No")
    exit()
  else:
    continue
print("Yes")


### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
for j in range(n-1):
  if h[j] - h[j+1] > 1:
    print("No")
    exit()
  elif h[j] == h[j+1] + 1:
    h[j+1] += 1
print("Yes")
from math import ceil, floor,gcd

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

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


Cdiff = floor(B/C) - floor((A-1)/C)
Ddiff = floor(B/D) - floor((A-1)/D)

CD = lcm(C,D)
CDdiff = floor(B/CD) - floor((A-1)/CD)



res = Cdiff+Ddiff-CDdiff
print((B-A+1)-res)



### FIXED CODE ###

from math import floor

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

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

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

def n(n):
    c = n // C
    d = n // D
    cd = n // lcm(C,D)
    return n - c - d + cd

print(n(B)-n(A-1))
code = input('security code: ')

num = (str)code.split('')

if num[0] == num[1]:
    print('Bad')
elif num[1] == num[2]:
    print('Bad')
elif num[2] == num[3]:
    print('Bad')
else:
    print('Good')

### FIXED CODE ###

num = input()
#num = str(code)

if num[0] == num[1] or num[1] == num[2] or num[2] == num[3]:
    print('Bad')
else:
    print('Good')
from collections import deque

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

tmp = [0 for _ in range(N + 1)]

if 1 not in A:
    tmp[1] = 1
    
if 2 not in A and N >= 2:
    tmp[2] = tmp[1] + 1

now = 0
for i in range(3, N+1):
    
    if i != A[now]:
        tmp[i] = tmp[i-1] + tmp[i-2] 
        
    else:
        if now < M - 1:
            now += 1
        

    
print(tmp[-1]%(10**9+7))




### FIXED CODE ###

from collections import deque

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

tmp = [0 for _ in range(N + 1)]

now = 0
if 1 not in A:
    tmp[1] = 1
    
else:
    now += 1
    
if (2 not in A) and N >= 2:
    tmp[2] = tmp[1] + 1
    
else:
    now += 1

for i in range(3, N+1):
    
    try:
        if i != A[now]:
            tmp[i] = tmp[i-1] + tmp[i-2] 
            
        else:
            now += 1
        
    except:
        tmp[i] = tmp[i-1] + tmp[i-2] 

    
print(tmp[-1]%(10**9+7))
from collections import*
n, m, *t = map(int, open(0).read().split())       
*w, s, t = [a-1for a in t]         
e = [[]for _ in range(n)]        
for u, v in zip(w[::2], w[1::2]):      
    e[u].append(v)

INF = 10**10
f = [[INF]*3for _ in range(n)]        
f[s][0] = 0        
q = deque([(s, 0)])           
while q:
    vi, j = q.popleft()         
    if vi == t and j == 0:
        print(f[vi][0]//3)
        break
    for ui in e[vi]:           
        if f[ui][(j+1)%3] < INF: continue           
        f[ui][(j+1)%3] = f[vi][j] + 1
        q.append((ui, (j+1)%3))
else:
    print(-1)

### FIXED CODE ###

def f_f(str):
    for s in str:
        if str.count(s) != 2:
            return False
    return True
 
S = input()
if f_f(S):
    print("Yes")
else:
    print("No")
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

N, M = MAP()
A = [input() for _ in range(M)]
B = [input() for _ in range(M)]

for i in range(N-M+1):
	for j in range(N-M+1):  #左上野ますが(i, j)
		tmp_lis = []
		for k in range(M):
			tmp_lis.append(A[i+k][j:j+M])
		if tmp_lis == B:
			print("Yes")
			exit()
else:
	print("No")

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()

A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

if A == B:
	print("Yes")
	exit()

flg = 1
for i in range(N-M):
	for j in range(N-M):
		for k in range(M):
			if A[i+k][j:j+M] != B[k]:
				break
		else:
			print("Yes")
			exit()
else:
	print("No")
import sympy
import math

n=int(raw_input())
m=sympy.factorint(math.factorial(n))
print m
res=1
v=m.values()
for i in xrange(len(v)):
 res*=v[i]+1
print res%(10**9+7)


### FIXED CODE ###

#ARC052C

n=int(raw_input())
s=[1 for i in range(n+1)]
res=1
for i in range(2,n+1):
 if s[i]:
  for j in range(i*2,n+1,i):
   s[j]=0
  cnt=0
  temp=n
  while temp:
   cnt+=temp/i
   temp/=i
  res=res*(cnt+1)%(10**9+7)
print res
print(*sorted(input().split())))

### FIXED CODE ###

l = list(input().split())
print(' '.join(map(str,sorted(l))))
import sys
input = sys.stdin.readline
from bisect import bisect
N=int(input())
X=[int(i) for i in input().split()]
L=int(input())
Q=int(input())
#T=[[int(i) for i in input().split()] for i in range(Q)]
T=[]
for i in range(Q):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    T.append((a-1,b-1))
F=[0]*N
for i in range(N):
    F[i]= bisect(X, X[i] + L) -1
#print(F)
dp=[ [N-1] * (N) for i in range(17)]

for i in range(N):
    #dp[0][i]=i
    dp[0][i]=F[i]
for c in range(1,17):
    for i in range(N):
        dp[c][i] = dp[c-1][ dp[c-1][i] ]
#print(dp)

def f(a,b):
    num=0
    t = a
    while True:
        for i in range(17):
            if dp[i][t]>=b:
                s=i
                break
        if s==0:
            num+=1
            break
        num += pow(2, s - 1)
        t = dp[s-1][t]
    print(num)
for a,b in T:
    f(a,b)



### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect
N=int(input())
X=[int(i) for i in input().split()]
L=int(input())
Q=int(input())
#T=[[int(i) for i in input().split()] for i in range(Q)]
T=[]
for i in range(Q):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    T.append((a-1,b-1))
F=[0]*N
for i in range(N):
    F[i]= bisect(X, X[i] + L) -1
#print(F)
dp=[ [N-1] * (N) for i in range(18)]

for i in range(N):
    #dp[0][i]=i
    dp[0][i]=F[i]
for c in range(1,18):
    for i in range(N):
        dp[c][i] = dp[c-1][ dp[c-1][i] ]
#print(dp)

def f(a,b):
    num=0
    t = a
    while True:
        for i in range(18):
            if dp[i][t]>=b:
                s=i
                break
        if s==0:
            num+=1
            break
        num += pow(2, s - 1)
        t = dp[s-1][t]
    print(num)
for a,b in T:
    f(a,b)
n = int(input())

g = [[-1 for j in range(n)] for i in range(n)]

for i in range(n):
	a = int(input())
	for _ in range(a):
		x, y = map(int, input().split())
		g[i][x-1] = y

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] != -1 && (s>>j&1) != g[i][j]:
                    ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)


### FIXED CODE ###

n = int(input())

g = [[-1 for j in range(n)] for i in range(n)]

for i in range(n):
	a = int(input())
	for _ in range(a):
		x, y = map(int, input().split())
		g[i][x-1] = y

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] == -1: continue
				if (s>>j&1) != g[i][j]: ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)
a,b,c,d = input()
count = 0
for i in range(a,b+1):
  if i % c == 0 or i % d == 0:
    continue
  count += 1

print(count)

### FIXED CODE ###

A,B,C,D = map(int, input().split())
from fractions import gcd

cd = C*D//gcd(D,C)
f = lambda x: B//x - ((A-1)//x)
print(B - A + 1 - (f(C) + f(D) - f(cd)))