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


def calc():
    a, b, c, d = map(int, raw_input().split())
    if a < b:
        return 'No'
    if d < b:
        return 'No'
    if c >= b:
        return 'Yes'
    a %= b
    s = set()
    while a not in s:
        s.add(a)
        a = (a + d) % b
        if a > c:
            return 'No'
    return 'Yes'


def main():
    t = input()
    for _ in range(t):
        print calc()


if __name__ == '__main__':
    main()


### FIXED CODE ###


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


def calc():
    a, b, c, d = map(int, raw_input().split())
    if a < b:
        return 'No'
    if d < b:
        return 'No'
    if c >= b:
        return 'Yes'
    g = gcd(b, d)
    a %= b
    n = (b - a) / g
    if a + g * n == b:
        n -= 1
    if a + g * n > c:
        return 'No'
    else:
        return 'Yes'


def main():
    t = input()
    for _ in range(t):
        print calc()


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

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))


x_dir = [[INF] * n for i in range(1 << n)]
y_dir = [[INF] * n for i in range(1 << n)]

for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state][i] = min(costs[i], x_dir[bit_state][i])
        y_dir[bit_state][i] = min(costs[i], y_dir[bit_state][i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state][j] = min(x_dir[bit_state][j], c * abs(yi - yj))
            y_dir[bit_state][j] = min(y_dir[bit_state][j], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit][i], y_dir[y_bit][i])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)

### FIXED CODE ###

#import random


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13

#n = 15
#info = []
#for i in range(n):
#    info.append([random.randint(-10000, 10000), random.randint(-10000, 10000), random.randint(1, 1000000)])


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))

OFFSET = n
x_dir = [INF] * ((1 << n) * OFFSET)
y_dir = [INF] * ((1 << n) * OFFSET)


for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state * OFFSET + i] = min(costs[i], x_dir[bit_state * OFFSET + i])
        y_dir[bit_state * OFFSET + i] = min(costs[i], y_dir[bit_state * OFFSET + i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state * OFFSET + j] = min(x_dir[bit_state * OFFSET + j], c * abs(yi - yj))
            y_dir[bit_state * OFFSET + j] = min(y_dir[bit_state * OFFSET + j], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit * OFFSET + i], y_dir[y_bit * OFFSET + i])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)
### BUGGY CODE ###

import copy

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
  b = copy.deepcopy(a)
  b.pop(i)
  for j in range(2,max(b)+1):
    c = list(map(lambda x: x % j,b))
    if sum(c) == 0 and j > ans:
      ans = j
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 1
if n == 2:
  print(max(a))
else:
  a0 = a[0]
  a1 = a[1]
  r = 0
  while True:
    r = a1 % a0
    if r == 0:
      b0 = a0
      break
    elif r > a0:
      a1, a0 = r, a0
    else:
      a1, a0 = a0, r
  a1 = a[1]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a1
    if r == 0:
      b1 = a1
      break
    elif r > a1:
      a2, a1 = r, a1
    else:
      a2, a1 = a1, r
  a0 = a[0]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a0
    if r == 0:
      b2 = a0
      break
    elif r > a0:
      a2, a0 = r, a0
    else:
      a2, a0 = a0, r
  max_a = max(b0,b1,b2)
  kouho = []
  for j in range(max_a,1,-1):
    if max_a % j == 0:
      c = list(map(lambda x: x % j,a))
      c_ng = [i for i in c if i > 0]
    #print("j=",j,"c=",c,"c_ng=",c_ng)
      if len(c_ng) <= 1:
        ans = j
        break
  print(ans)
### BUGGY CODE ###

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

m = max(a)
ans = [0 for _ in range(m)]
azk = [0 for _ in range(m)]

for i in range(m):
    ans[i] = a.count(i + 1)
    azk[i] = round(ans[i] * (ans[i] - 1) / 2)
dic = {}

for i in range(n):
    ppt = 0
    if a[i] in dic:
        print(dic[a[i]])
        continue
    for j in range(m):
        if (j + 1) == a[i]:
            ppt += round((ans[j] - 1)*(ans[j] - 2) / 2)
        else:
            ppt += azk[j]
    dic[a[i]] = ppt
    print(ppt)


### FIXED CODE ###

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

b = [0 for _ in range(max(a))]
for i in a:
    b[i - 1] += 1
ans = 0
for i in b:
    ans += int(i * (i-1) / 2)

for i in a:
    print(ans - (b[i - 1] - 1))
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def digit_dp(n, f):
    l = len(str(n))
    dp = [[[0] * f for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        max_d = int(str(n)[i])
        for j in range(2):
            for k in range(f):
                for d in range(10 if j else max_d + 1):
                    dp[i + 1][j or (d < max_d)][(k + d) % f] += dp[i][j][k]
                    dp[i + 1][j or (d < max_d)][(k + d) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


k = I()
d = I()
print(digit_dp(k, d) % mod)


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def digit_dp(n, f):
    dp = [[[0] * f for _ in range(2)] for _ in range(10002)]
    dp[0][0][0] = 1
    l = len(n)
    for i in range(l):
        max_d = int(n[i])
        for j in range(2):
            for ki in range(f):
                for di in range(10 if j else max_d + 1):
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] += dp[i][j][ki]
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


k = input()
d = int(input())
print(digit_dp(k, d) % mod)
### BUGGY CODE ###

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

sdot = ['']
ssphas = s.split('.')
sspdot = s.split('#')
num = min(s.count('.'),s.count('#') - len(ssphas[-1]))
if s[0] == '.':
    sdot.extend(ssphas)
for i in range(len(ssphas)):
    num = min(len(''.join(ssphas[0:i + 1]) + ''.join(sspdot[i + 1:-1])),num)
print(num)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
narabi = []
befores = '#'
for S in s:
    if S == befores:
        cnt += 1
    else:
        narabi.append(cnt)
        befores = S
        cnt = 1
narabi.append(cnt)
if s[-1] == '#':
    narabi.append(0)
hennkann = s.count('.')
saishou = s.count('.')
hashu = 0
dot = 1
for i in range(int(len(narabi) / 2)):
    hennkann = hennkann - narabi[dot] + narabi[hashu]
    saishou = min(saishou,hennkann)
    dot += 2
    hashu += 2
print(saishou)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import math

big = 10**9 + 7

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

A = []
for a in row_A:
    A.append(a%big)


num = A[0]
set_A = set(A)

for a in set_A:
    num = num * a // math.gcd(num, a)

res = 0
for a in A:
    res += num//a % big

print(res%big)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

def main():
    big = 10 ** 9 + 7

    N = int(input())
    A = list(map(int, input().split()))
    num = A[0]
    for i in range(1, N):
        num = num * A[i] // math.gcd(num, A[i])

    res = 0
    for a in A:
        res += num // a

    print(res % big)

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

s=input().split()

N=int(s[0])
K=int(s[1])

if N > K/2 and N < K:
    print(abs(N-K))

if N <= K/2:
    print(N)

if N==K:
    print(0)

while N > 1000*K:
    N=N-1000*K
    if N <=1000*K:
        break

while N > 100*K:
    N=N-100*K
    if N <=100*K:
        break

if N > K:
    while N > K:
        N=N-K
        if N <= K:
            break

    if N > K/2 and N < K:
        print(abs(N-K))

    if N <= K/2:
        print(N)

    if N==K:
        print(0)
    




### FIXED CODE ###

s=input().split()

N=int(s[0])
K=int(s[1])

if N > K/2 and N < K:
    print(abs(N-K))

if N <= K/2:
    print(N)

if N==K:
    print(0)



if N > K:

    


    if N >2*K:
        L=N//K
        N=N-L*K
    else:
        N=N-K
    

    if N > K/2 and N < K:
        print(abs(N-K))

    if N <= K/2:
        print(N)

    if N==K:
        print(0)
### BUGGY CODE ###

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

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


def append_candidate(a, b):
    if b not in candidate[a] and b not in friend[a] and b != a:
        candidate[a].append(b)
    if a not in candidate[b] and a not in friend[b] and a != b:
        candidate[b].append(a)


def update_candidate(a, b):
    for af in friend[a]:
        append_candidate(af, b)
        for bf in friend[b]:
            append_candidate(af, bf)
        for bc in candidate[b]:
            append_candidate(af, bc)

    for ac in candidate[a]:
        append_candidate(ac, b)
        for bf in friend[b]:
            append_candidate(ac, bf)
        for bc in candidate[b]:
            append_candidate(ac, bc)


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

    if a in candidate[b]:
        candidate[b].remove(a)
    if b in candidate[a]:
        candidate[a].remove(b)

    friend[a].append(b)
    friend[b].append(a)

    update_candidate(a, b)
    update_candidate(b, a)

for i in range(k):
    c, d = map(int, input().split())
    if c in candidate[d]:
        candidate[d].remove(c)
    if d in candidate[c]:
        candidate[c].remove(d)

print(' '.join(str(len(candidate[i])) for i in range(1, n+1)))


### FIXED CODE ###

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


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

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]

uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

    uf.union(a-1, b-1)

for i in range(k):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

candidate = [0] * n

for i in range(n):
    candidate[i] = uf.get_size(i) - len(friend[i]) - 1
    for j in block[i]:
        if uf.is_same(i, j):
            candidate[i] -= 1

print(' '.join(list(map(str, candidate))))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 22:06:14 2020

@author: Masataka Amau
"""

N = int(input())
aaa = []
for i in range(N):
    buf = input()
    if(buf not in aaa):
        aaa.append(buf)
        
print(len(aaa))

### FIXED CODE ###

d = {}
ans = 0;
N = int(input())
for i in range(N):
    key = input()
    if key not in d:
        ans+=1
        d[key] = 0
        
        
print(ans)
### BUGGY CODE ###

N = int(input())

lnam = list()
lnum = list()

for i in range(N):
    s = input()
    if s in lnam:
        lnum[lnam.index(s)] += 1
    else:
        lnam.append(s)
        lnum.append(1)

lall = list(zip(lnum, lnam))

fms = max(lnum)

lwin = list()
for i in range(len(lall)):
    if lall[i][0] == fms:
        lwin.append(lall[i][1])

lwin.sort()
for i in range(len(lwin)):
    print(lwin[i])

### FIXED CODE ###

n = int(input())

d = {}

for i in range(n):
    s = input()
    d[s] = d.get(s, 0) + 1

m = max(d[i] for i in d)

for j in sorted(d):
    if d[j] == m:
        print(j)
### BUGGY CODE ###

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

for i in range(n-k+1):
  ans=max(ans,sum(a[i:i+k]))
  
ans+=k
ans/=2

print(ans)

### FIXED CODE ###

import itertools

n,k=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x:(x+1)/2,a))

a=[0]+list(itertools.accumulate(a))
ans=0

for i in range(n-k+1):
  ans=max(ans,a[i+k]-a[i])
  
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ma = max(A)
xma = 1
for i in range(20):
    xma = xma  * 2
    if xma >= ma:
        break
ans = 0
a = 0
max_flag = False
for l in range(N):
    a = A[l]
    x = A[l]
    for j in range(l+1,N):
        a += A[j]
        x = x ^ A[j]
        if a == x:
            ans += 1
        else:
            break
print(ans + N)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
num = 0
a = 0
x = 0
k = 0
for l in range(N):
    for j in range(k,N):
        a += A[j]
        x =  x ^ A[j]
        if a  != x:
            ans += j - l
            k = j
            x = x ^ A[l] ^ A[j]
            a = a - A[l] - A[j]
            break
        elif j == N-1:
            ans += N-l
            k = j
            x = x ^ A[l] ^ A[j]
            a = a - A[l] - A[j]
print(ans )
### BUGGY CODE ###

N,M,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]

for i in range(N):
    a.append(a[i] + A[i])
for j in range(M):
    b.append(b[j] + B[j])
ans = 0
for i in range(N+1):
    for j in range(M+1):
        if a[i] + b[j] <= K:
            ans = max(ans, i+j)
print(ans)

### FIXED CODE ###

N,M,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]

for i in range(N):
    a.append(a[i] + A[i])
for j in range(M):
    b.append(b[j] + B[j])
ans = 0
j = M
for i in range(N+1):
    if a[i] > K:
        break
    while a[i] + b[j] > K:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
for i in range(1, N):
    if H[i] < max(H[:i]) - 1:
        print("No")
        exit()
print("Yes")


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
M = 0
for i in range(1, N):
    M = max(M, H[i - 1])
    if H[i] < M - 1:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

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

def check(d):#そいつが必要か
    global a,n,k
    dp=[0]*(k)#k-1まで
    if a[d]>=k:
        return True
    for i in range(n):
        if i!=d:
            dp_sub=[0]*(k)
            for j in range(k-1):
                if j==0 or dp[j]!=0:
                    if j+a[i]<k:
                        dp_sub[j+a[i]]=1
                    else:
                        break
            for j in range(k):
                if dp_sub[j]==1:
                    dp[j]=1
                    if j+a[d]>=k:
                        return True
    return False
l,r=0,n-1
while l+1<r:
    d=(l+r)//2
    if check(d):#必要か
        r=d
    else:
        l=d
if check(l):
    print(l)
else:
    if check(r):
        print(r)
    else:
        print(r+1)

### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
ans = N
t = 0

for i in range(N-1, -1, -1) :
    if t+a[i] < K :
        t += a[i]
    else :
        ans = min(ans, i)
 
print(ans)
### BUGGY CODE ###

N=int(input());tt=0
while(N):tt+=(N%10);N//=10
print("No" if tt%9 else "Yes")

### FIXED CODE ###

print("No"if int(input())%9 else "Yes")
### BUGGY CODE ###

N = int(input())
An = list(map(int, input().split()))
Q = int(input())


for i in range(Q):
    b, c = map(int, input().split())
    for j, name in enumerate(An):
        if An[j] == b:
            An[j] = c
    
    print(sum(An))

### FIXED CODE ###

N = int(input())

An = list(map(int, input().split()))
Q = int(input())

L = [0] * 100001
for item in An:
    L[item] += 1

sum = sum(An)

for i in range(Q):
    b, c = map(int, input().split())
    sum += (c-b) * L[b]
    L[c] += L[b]
    L[b] = 0
    print(sum)
### BUGGY CODE ###

def solve(i, m):
    if m == 0: return True
    if i >=n: return False
    res = solve(i + 1, m) or solve(i + 1, m - A[i])
    return res

n = int(input())
A = [int(x) for x in input().split()]
q = int(input())
M = [int(x) for x in input().split()]

for m in M:
    if solve(0, m):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

def power_set(item_lists):

    p_sets = [[]]

    for item in item_lists:
        tmp = []
        for element in p_sets:
            tmp.append(element + [item])
        p_sets.extend(tmp)

    return p_sets



if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    m = list(map(int, input().split()))

    p_set = [sum(l) for l in power_set(A)]

    for m_i in m:

        if m_i in p_set:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

import sys
n,m = map(int,input().split())
ls = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    if i not in ls:
        dp[i] = (dp[i-1]+dp[i-2])
        if dp[i] >= 10**9+7:
            dp[i] %= 10**9+7 
    else:
        if i-1 in ls:
            print(0)
            sys.exit()
print(dp[-1])

### FIXED CODE ###

import sys
n,m = map(int,input().split())
ls = set(int(input()) for _ in range(m))
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    if i not in ls:
        dp[i] = (dp[i-1]+dp[i-2])
        if dp[i] >= 10**9+7:
            dp[i] %= 10**9+7 
    else:
        if i-1 in ls:
            print(0)
            sys.exit()
print(dp[-1])
### BUGGY CODE ###

X,Y = map(int,input().split())

if X==Y:
    print(-1)
else:
    for i in range(10**18):
        X1 = int(X*i)
        if X1 % Y != 0:
            print(str(X1))
            break
    



### FIXED CODE ###

X, Y = map(int, input().split())

if X % Y == 0:
    print(-1)
else:
   print(X)
### BUGGY CODE ###

S = input()[::-1]

cnts = [0]*2019

cnts[0] = 1

num = 0

d = 1

ans = 0

for i in S:
    num += int(i) * d
    d *= 10
    num %= 2019
    cnts[num] += 1

for j in cnts:
    ans += j * (j-1) // 2 

print(ans)

### FIXED CODE ###

S = input()[::-1]

cnts = [0]*2019
cnts[0] = 1
num = 0
d = 1
ans = 0

for i in S:
    num += int(i) * d
    d *= 10
    num %= 2019
    d %= 2019
    cnts[num] += 1

for j in cnts:
    ans += j * (j-1) // 2 

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

#input
a = list(map(int,input().split())) #input from array of integer like "1 2 3"
n = a[3]
a = a[:3]
range_r = n//a[0]+1
range_g = n//a[1]+1
cnt = 0
for r in range(range_r):
  for g in range(range_g):
    rg = r*a[0]+g*a[1]
    if rg > n:
      break
    if (n - rg)%a[2]==0:
      cnt += 1

print(cnt)

### FIXED CODE ###

#input
a = list(map(int,input().split())) #input from array of integer like "1 2 3"
n = a[3]
a = a[:3]
range_r = n//a[0]+1
range_g = n//a[1]+1
cnt = 0
for r in range(range_r):
  for g in range((n-r*a[0])//a[1]+1):
    rg = r*a[0]+g*a[1]
    if (n - rg)%a[2]==0:
      cnt += 1

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

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

def nibunki_left(L, s, f, p):
	cent = (f-s)//2 + s
	if s == f:
		return s
	elif s+1 == f:
		if L[s] > p:
			return s
		else:
			return f

	if L[cent] <= p:
		return nibunki_left(L, cent, f, p)
	else:
		return nibunki_left(L, s, cent, p)

def nibunki_right(L, s, f, p):
	cent = (f-s)//2 + s
	if s == f:
		return f
	elif s+1 == f:
		if L[f] < p:
			return f
		else:
			return s

	if L[cent] < p:
		return nibunki_right(L, cent, f, p)
	else:
		return nibunki_right(L, s, cent, p)



ans = 0

for a in range(N-2):
	for b in range(a+1, N-1):
		l = max(L[a] - L[b], L[b] - L[a])
		r = L[a] + L[b]

		l_ind = nibunki_left(L, 0, N-1, l)
		r_ind = nibunki_right(L, 0, N-1, r)

		if l_ind <= b and r_ind <= b:
			continue
		elif l_ind <= b and r_ind > b:
			ans += r_ind - b
		elif l_ind > b and r_ind > b:
			ans += r_ind - l_ind + 1


print(ans)

### FIXED CODE ###

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

def BinaryIndexSearch_floor(p, SL):
	"""
	search the minimum number among the larger numbers than the ginven nymber "n". 
	return the index of it under the list sorted.
	"""
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] > p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[l] > p:
				return l
			elif SL[r] > p:
				return r
			else:
				return -1

		center = l + ((r-l) // 2)

		if SL[center] <= p:
			l = center + 1
			continue

		else:
			r = center
			continue

def BinaryIndexSearch_ceil(p, SL):
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] < p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[r] < p:
				return r
			elif SL[l] < p:
				return l
			else:
				return -1
		center = l + ((r-l) // 2)

		if SL[center] < p:
			l = center 
			continue

		else:
			r = center - 1
			continue
ans = 0
for i in range(N-1):
	for j in range(i+1,N):
		wa = L[i] + L[j]
		sa = abs(L[i]-L[j])

		l = BinaryIndexSearch_ceil(wa,L)
		s = BinaryIndexSearch_floor(sa,L)

		oc = 0
		if s <= i <= l:
			oc += 1
		if s <= j <= l:
			oc += 1
		if l >= s:
			ans += max(0, l-s+1-oc)

print(ans//3)