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

def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
l=1
for a in A:
  l=lcd(l,a)
ans=0
for a in A:
  ans=(ans+l//a)
print(ans%1000000007)

### FIXED CODE ###

P=1000000007
def power(x,p):
  if(p==0):
    return 1;
  if(p%2):
    return power(x,p-1)*x%P;
  a=power(x,p//2);
  return a*a%P;
def inv(x):
  return power(x,P-2);
N=int(input());A=list(map(int,input().split()));
#N=10000;A=[1000000 for i in range(N)];
L=[0 for i in range(max(A)+1)]
for a in A:
  t=a;i=2;
  while(i**2<=a):
    c=0;
    while(t%i==0):
      t//=i;c+=1;
    L[i]=max(L[i],c)
    i+=1;
  if(t!=1):
    L[t]=max(L[t],1)
    
l=1;
for i in range(2,len(L)):
  l=l*power(i,L[i])%P;
b=0;
for a in A:
  b=(b+inv(a))%P
print(l*b%P)
### BUGGY CODE ###

n = int(input())

print(0)
s0 = str(input())

print(n-1)

def is_ok(x):
    print(x)
    s = str(input())
    if s == s0:
        return False
    else:
        return True

l = 1
r = n-2
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        r = c
    else:
        l = c


### FIXED CODE ###

def main():
    n = int(input())

    def q(i):
        print(i, )
        s = str(input())
        if s == 'Vacant':
            exit()
        else:
            return s

    x = q(n-1)
    x = q(0)

    def ok(m):
        if m == 0:
            return False
        else:
            if (m%2 == 0 and q(m) != x) or (m%2 == 1 and q(m) == x):
                return True
            else:
                return False

    l = 0
    r = n-1
    while l+1 < r:
        c = (l+r)//2
        if ok(c):
            r = c
        else:
            l = c

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

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    ga, sa, ba = map(int, input().split())
    gb, sb, bb = map(int, input().split())

    ans = 0
    flags = [ga >= gb, sa >= sb, ba >= bb]

    for x in [range(N//ga+1), [0]][flags[0]]:
        # yl = [range((N-ga*x)//sa+1), [0]][flags[1]]
        for y in [range((N-ga*x)//sa+1), [0]][flags[1]]:
            for z in [range((N-ga*x-sa*y)//ba+1), [0]][flags[2]]:
                M = N + (gb-ga)*x + (sb-sa)*y + (bb-ba)*z# 取引所Bでのどんぐりの数
                for p in [[0], range(M//gb+1)][flags[0]]:
                    for q in [[0], range((M-gb*p)//sb+1)][flags[1]]:
                        for r in [[0], range((M-gb*p-sb*q)//bb+1)][flags[2]]:
                            ans = max(ans, M+(ga-gb)*p+(sa-sb)*q+(ba-bb)*r)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    gsba = list(map(int, input().split()))
    gsbb = list(map(int, input().split()))
    
    # ナップザック問題として解く
    w = gsba
    v = [gsbb[i]-gsba[i] for i in range(3)]
    dp = [0]*(N+1)

    for i in range(3):
        for j in range(N+1):
            if j >= w[i]:
                dp[j] = max(dp[j],dp[j-w[i]]+v[i])

    M = dp[-1] + N
    w = gsbb
    v = [gsba[i]-gsbb[i] for i in range(3)]
    dp = [0]*(M+1)

    for i in range(3):
        for j in range(M+1):
            if j >= w[i]:
                dp[j] = max(dp[j],dp[j-w[i]]+v[i])

    print(dp[-1] + M)

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

from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = {}
for i in range(N):
    edge_map[i] = deque([])

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0 for i in range(N)]

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

def dfs_res(idx, parent, diff):
    global res_list
    global counters
    if calculated[i]:
        return res_list[idx]
    res = counters[idx] + diff
    res_list[idx] = res
    calculated[idx] = True
    for child in edge_map[idx]:
        if child == parent:
            continue
        dfs_res(child, idx, res)
    return

dfs_res(0, None, 0)

ans = " ".join([str(i) for i in res_list])
print(ans)


### FIXED CODE ###

from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0]*N

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]

print(*res_list)
### BUGGY CODE ###

N, M = map(int,input().split())
ABs = list([list(map(int,input().split())) for _ in range(M)])
 
ship1 =[]
shipn =[]
 
for ab in ABs:
    if ab[0]==1:ship1.append(ab[1])
    elif ab[1]==N:shipn.append(ab[0])

jdg=False      
      
for j in ship1:
    if j in shipn:jdg=True
if jdg:print('POSSIBLE')
else:print('IMPOSSIBLE')

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
ABs = list([list(map(int,input().split())) for _ in range(M)])
 
ship1 =[]
shipn =[]
 
for ab in ABs:
    if ab[0]==1:ship1.append(ab[1])
    elif ab[1]==N:shipn.append(ab[0])
 
      
if list(set(ship1) & set(shipn)) ==[]:print('IMPOSSIBLE')
else:print('POSSIBLE')
### BUGGY CODE ###

def invNum(d,A):
    if d < 0 or len(A)==0: return 0
    cnt = 0
    L = []
    R = []
    for ai in A:
        if ai < 2**d:
            L.append(ai)
            cnt += len(R)
        else:
            R.append(ai-2**d)
    return cnt + invNum(d-1,L) + invNum(d-1,R)
 
if __name__=='__main__':
    n = int(input()) 
    print(invNum(29,list(map(int,input().split()))))

### FIXED CODE ###

cnt = 0
def merge(L,R):
    global cnt
    n = len(L)+len(R)
    lenL = len(L)
    A = []
    i = j = 0
    L.append(-1)
    R.append(-1)
    for _ in range(n):
        if L[i] > R[j]:
            A.append(L[i])
            i += 1
        else:
            A.append(R[j])
            j += 1
            cnt += lenL-i
    return A

def mergeSort(A):
    if len(A)==1: return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:])) 

if __name__=='__main__':
    n = int(input()) 
    A = list(map(int,input().split()))
    mergeSort(A[::-1])
    print(cnt)
### BUGGY CODE ###

from __future__ import print_function
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0]*(n + 1) for a in range(m + 2)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(max(c))

n = int(raw_input().rstrip())
strs = stdin.readlines()
ret = []
for i in range(n):
    s1 = strs[i*2].rstrip()
    s2 = strs[i*2+1].rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

### FIXED CODE ###

def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = x[i]
        c2 = c1[:]
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
   
n = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")
### BUGGY CODE ###

N = int(input())
T = [[] for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a].append([b,c])
    T[b].append([a,c])

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [t + [K] for t in T[K]]


for _ in range(Q):
    x, y = map(int, input().split())

    while len(queue) > 0 and (shortest_path[x] == 0 or shortest_path[y] ==0):
        v = queue.pop(0)
        shortest_path[v[0]] = v[1]
        for u in T[v[0]]:
            if u[0] != v[2]:
                queue.append([u[0], u[1] + v[1], v[0]])
    
    print(shortest_path[x] + shortest_path[y])

### FIXED CODE ###

from collections import deque

N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x] + shortest_path[y])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ls = [0]*N
for i in range(N):
    ls[i] = A.index(i+1)+1
print(*ls)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ls = [0]*N
for i in range(N):
    ls[A[i]-1] = i+1
print(*ls)
### BUGGY CODE ###

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

for _ in range(K):
  A, B, C = B+C, A+C, A+B

ans = A - B
if ans > 1e18:
  print("Unfair")
else:
  print(ans)


### FIXED CODE ###

A, B, C, K = map(int, input().split())
  
ans = [A - B, B - A][K%2]
if ans > 1e18:
  print("Unfair")
else:
  print(ans)
### BUGGY CODE ###

h , w = map(int,input().split())
s = [input() for i in range(h)]
coulef = [[0 for i in range(w)] for j in range(h)]
courig = [[0 for i in range(w)] for j in range(h)]
coudow = [[0 for i in range(w)] for j in range(h)]
couup = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    cou = 0
    for j in range(w):
        if s[i][j] == ".":
            cou += 1
            courig[i][j] = cou
        elif s[i][j] == "#":
            cou = 0
for i in range(h):
    cou = 0
    for j in reversed(range(w)):
        if s[i][j] == ".":
            cou += 1
            coulef[i][j] = cou
        elif s[i][j] == "#":
            cou = 0
for i in range(w):
    cou = 0
    for j in range(h):
        if s[j][i] == ".":
            cou += 1
            coudow[j][i] = cou
        elif s[j][i] == "#":
            cou = 0
for i in range(w):
    cou = 0
    for j in reversed(range(h)):
        if s[j][i] == ".":
            cou += 1
            couup[j][i] = cou
        elif s[j][i] == "#":
            cou = 0

ans = 0
for i in range(h):
    for j in range(w):
        now = couup[i][j]+coudow[i][j]+coulef[i][j]+courig[i][j]
        ans = max(ans,now-3)
print(ans)

### FIXED CODE ###

h , w = map(int,input().split())
giri = [list(input()) for i in range(h)]
ans = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    sta = -1
    cou = 0
    for j in range(w):
        if sta == -1 and giri[i][j] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[i][j] == ".":
            cou += 1
        elif sta != -1 and giri[i][j] == "#":
            for k in range(sta,j):
                ans[i][k] += cou
            cou = 0
            sta = -1
        if j == w-1 and sta != -1:
            for k in range(sta,w):
                ans[i][k] += cou

for i in range(w):
    sta = -1
    cou = 0
    for j in range(h):
        if sta == -1 and giri[j][i] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[j][i] == ".":
            cou += 1
        elif sta != -1 and giri[j][i] == "#":
            for k in range(sta,j):
                ans[k][i] += cou
            cou = 0
            sta = -1
        if j == h-1 and sta != -1:
            for k in range(sta,h):
                ans[k][i] += cou

kotae = 0

for i in range(h):
    for j in range(w):
        kotae = max(kotae,ans[i][j]-1)

print(kotae)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
DP = []
for i in range(min(N, K + 1)):
    DP.append(abs(H[0] - H[i]))
for i in range(K + 1, N):
    diff = float("inf")
    for d in range(1, K + 1):
        diff = min(diff, DP[-d] + abs(H[i - d] - H[i]))
    DP.append(diff)
print(DP[-1])


### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
DP = []
for i in range(min(N, K + 1)):
    DP.append(abs(H[0] - H[i]))
for i in range(K + 1, N):
    diff = float("inf")
    for d in range(1, K + 1):
        diff = min(diff, DP[-d] + abs(H[i - d] - H[i]))
    DP.append(diff)
print(DP[-1])
### BUGGY CODE ###

s = int(input())

x1, y1 = 0, 0
x2, y2, x3, y3 = 0, 0, 0, 0

while True:
    if s >= 10e9:
        for i in range(int(s**0.5), 0, -1):
            if s % i == 0 and i <= 10e9 and s / i <= 10e9:
                x2 = i
                y3 = s//i
                break
    else:
        for i in range(1, int(s**0.5) + 1):
            if s % i == 0 and i <= 10e9 and s / i <= 10e9:
                x2 = i - x1
                y3 = s//i
                break

    if x2 == 0 and y3 == 0:
        y2 = -1
        x3 += 1
        s -= x3
        continue
    break

print(x1, y1, x2, y2, x3, y3)


### FIXED CODE ###

s = int(input())

e = 10**9
if s == e**2:
    print(0, 0, e, 1, 0, e)
else:
    y = s//e + 1
    x = y*e - s
    print(0, 0, e, 1, x, y)
### BUGGY CODE ###

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

A_accumulate_cost = [0]
lastCost = 0
for i in range(N):
    lastCost += A[i]
    A_accumulate_cost.append(lastCost)

B_accumulate_cost = [0]
lastCost = 0
for i in range(M):
    lastCost += B[i]
    B_accumulate_cost.append(lastCost)

max_num = 0
for i in range(N, -1, -1):
    A_cost = A_accumulate_cost[i]
    if (A_cost > K):
        continue

    for j in range(M, -1, -1):
        if (A_cost + B_accumulate_cost[j] <= K):
            if (i + j > max_num):
                max_num = i+j
            break

print(max_num)

### FIXED CODE ###

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

A_accumulate_cost = [0]
lastCost = 0
for i in range(N):
    lastCost += A[i]
    A_accumulate_cost.append(lastCost)

B_accumulate_cost = [0]
lastCost = 0
for i in range(M):
    lastCost += B[i]
    B_accumulate_cost.append(lastCost)

max_num = 0
p = M
for i in range(N+1):
    A_cost = A_accumulate_cost[i]
    if A_cost > K:
        break

    for j in range(p, -1, -1):
        if A_cost + B_accumulate_cost[j] <= K:
            p = j
            if i + j > max_num:
                max_num = i+j
            break

print(max_num)
### BUGGY CODE ###

def bknap(curw,wei,val,n):
 if(n==0 or curw==0):
  return 0
 if(wei[n-1]>curw):
  return bknap(curw,wei,val,n-1)
 else:
  return max(val[n-1]+bknap(curw-wei[n-1],wei,val,n-1),bknap(curw,wei,val,n-1))
n,w=map(int,input().split())
wei=[]
val=[]
for i in range(n):
 w1,v1=map(int,input().split())
 wei.append(w1)
 val.append(v1)
print(bknap(w,wei,val,n))

  


### FIXED CODE ###

import sys
input=sys.stdin.readline
def fun(n,w):
 cos=[0]*(w+1)
 for i in range(n):
  w1,v1=map(int,input().split())
  for j in range(w,w1-1,-1):
   f=cos[j-w1]+v1
   if(cos[j]<f):
    cos[j]=f
 print(cos[-1])
n,w=map(int,input().split())
fun(n,w)
### BUGGY CODE ###

MOD = 10**9+7
N = int(input())
L = list(map(lambda x: bin(int(x))[2:], input().split()))
max_len = max([len(v) for v in L])
padL = ["0"*(max_len-len(v))+v for v in L]
cnt = [0]*max_len
for i in range(max_len):
    for l in padL:
        cnt[i] += 1 if l[i] == "1" else 0

ans = 0
v = 1
for i in range(max_len):
    ans += v*cnt[max_len-1-i]*(N-cnt[max_len-i-1])
    ans %= MOD
    v *= 2

print(ans)


### FIXED CODE ###

MOD = 10**9+7
N = int(input())
L = list(map(lambda x: bin(int(x))[2:], input().split()))
max_len = max([len(v) for v in L])
padL = ["0"*(max_len-len(v))+v for v in L]
cnt = [0]*max_len
for i in range(max_len):
    for l in padL:
        cnt[i] += 1 if l[i] == "1" else 0

ans = 0
v = 1
for i in range(max_len):
    ans += v*cnt[max_len-1-i]*(N-cnt[max_len-i-1])
    ans %= MOD
    v *= 2

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

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

for i in range(1, N+1):
    print(A.index(i) + 1, end=' ')

### FIXED CODE ###

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

B = [0] * N
for i in range(0, N):
    B[A[i]-1] = i+1
[print(x, end=' ') for x in B]
### BUGGY CODE ###

#!/usr/bin/env python3

R, C, K = list(map(int, input().split()))

V = [[] for i in range(R)]
for i in range(K):
    r, c, v = list(map(int, input().split()))
    V[r-1].append([c, v])


# dp = [[[0 for j in range(R+1)] for i in range(C+1)]

# print(rck)
dp = [0] * (C+1)
for r in range(1, R+1):
    tmp0 = 0
    tmp1 = 0
    tmp2 = 0
    tmp3 = 0
    V[r-1].sort()
    for c, v in V[r-1]:
        tmp0 = max(dp[c], tmp0)
        tmp1 = max(dp[c], tmp1)
        tmp2 = max(dp[c], tmp2)
        tmp3 = max(dp[c], tmp3)

        tmp3 = max(tmp3, tmp2+v)
        tmp2 = max(tmp2, tmp1+v)
        tmp1 = max(tmp1, tmp0+v)

        dp[c] = max(tmp0, tmp1, tmp2, tmp3)
    for i in range(1, C+1):
        dp[i] = max(dp[i], dp[i-1])
    # print(dp)

print(dp[-1])


### FIXED CODE ###

#!/usr/bin/env python3

R, C, K = list(map(int, input().split()))

V = [[] for i in range(R)]
for i in range(K):
    r, c, v = list(map(int, input().split()))
    V[r-1].append([c, v])


# dp = [[[0 for j in range(R+1)] for i in range(C+1)]

# print(rck)
dp = [0] * (C+1)
for r in range(1, R+1):
    tmp0 = 0
    tmp1 = 0
    tmp2 = 0
    tmp3 = 0
    V[r-1].sort()
    for c, v in V[r-1]:
        tmp0 = max(dp[c], tmp0)
        tmp1 = max(dp[c], tmp1)
        tmp2 = max(dp[c], tmp2)
        tmp3 = max(dp[c], tmp3)

        tmp3 = max(tmp3, tmp2+v)
        tmp2 = max(tmp2, tmp1+v)
        tmp1 = max(tmp1, tmp0+v)

        dp[c] = max(tmp0, tmp1, tmp2, tmp3)
    for i in range(1, C+1):
        dp[i] = max(dp[i], dp[i-1])
    # print(dp)

print(dp[-1])
### BUGGY CODE ###

Period, WorkingDay, PausePeriod = map(int, input().split())
PassionDays = input()

"""
Calculate the day that you can work the fastest and the day that you can work
the slowest. If two days coincide, that day is always a working day.
"""
earliest_days = [-1 for _ in range(Period)]
slowest_days = [-2 for _ in range(Period)]

for days in (earliest_days, slowest_days):
    
    if days == earliest_days:
        i_day = 0
        i_work_day = 1
        pause_period = PausePeriod
        diff_from_next = 1
    else:
        i_day = Period - 1
        i_work_day = WorkingDay
        pause_period = PausePeriod * (-1)
        diff_from_next = -1
    
    while 1 <= i_work_day and i_work_day <= WorkingDay:
        if PassionDays[i_day] == 'o':
            days[i_day] = i_work_day
            i_work_day += diff_from_next
            i_day += pause_period
        i_day += diff_from_next

for earliest_day, slowest_day in zip(earliest_days, slowest_days):
    if earliest_day == slowest_day:
        print(earliest_days.index(earliest_day) + 1)

exit()

### FIXED CODE ###

N, K, C = map(int, input().split())
S = input()
S_reverse = S[::-1]

left_justified = [-1 for _ in range(N)]
right_justified = [-2 for _ in range(N)]

for i_justified in (left_justified, right_justified):
    if i_justified == left_justified:
        i_S = S
        nearest_position = 1
        positioning = 1
    else:
        i_S = S_reverse
        nearest_position = K
        positioning = -1
    
    i_K = 0
    
    while i_K <= N-1:
        if i_S[i_K] == 'o':
            i_justified[i_K] = nearest_position
            i_K += C
            nearest_position += positioning
        i_K += 1

for i_N in range(N):
    if left_justified[i_N] == right_justified[N - i_N - 1]:
        print(i_N + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

class RangeAddQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        # 初期値
        self.data = [0]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                self.data[r-1] += v
            if l&1:
                self.data[l-1] += v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = 0
        while i+1:
            if self.data[i]:
                res += self.data[i]
            # (i-1)//2
            i = ~-i//2
        return res

label = [-1]*n
cnt = [0]
def dfs(i):
    if label[i] != -1:
        return
    label[i] = cnt[0]
    cnt[0] += 1
    for to in G[i]:
        dfs(to)

dfs(0)

nG = [[] for i in range(n)]
for i in range(n):
    for j in G[i]:
        nG[label[i]].append(label[j])

pos = [0]*n
cnt = [0]
vis = [False]*n
def dfs2(v):
    if vis[v]:
        return
    vis[v] = True
    order = cnt[0]
    cnt[0] += 1
    for to in nG[v]:
        dfs2(to)
    pos[order] = cnt[0]

dfs2(0)

RAQ = RangeAddQuery(n)

ans = []
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    v = label[p]
    RAQ.update(v, pos[v], x)

ans = [0]*n
for i in range(n):
    v = label[i]
    b = RAQ.query(v)
    ans[i] = b

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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


a = [0]*n
for i in range(q):
    p,x = map(int, input().split())
    p -= 1
    a[p] += x

# bfs
from collections import deque
q = deque()
q.append((0,0))
visited = [0]*n
ans = [0]*n
while q:
    cur, cost = q.popleft()
    if visited[cur]:
        continue
    visited[cur] = 1
    cost += a[cur]
    ans[cur] = cost
    for to in G[cur]:
        if not visited[to]:
            q.append((to, cost))

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


code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False


cdef extern from "<atcoder/math>" namespace "atcoder":
    long long floor_sum(long long n, long long m, long long a, long long b)

cpdef long long FloorSum(long long n, long long m, long long a, long long b):
    return FloorSum(n, m, a, b)
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import FloorSum

def main():
    T = int(input())
    for i in range(T):
        n,m,a,b = list(map(int,input().split()))
        print(FloorSum(n, m, a, b))

main()

### FIXED CODE ###

def FloorSum(n,m,a,b):
    ret = 0
    while True:
        if a>=m:
            ret += (n-1)*n*(a//m)//2
            a%=m

        if b>=m:
            ret += n*(b//m)
            b%=m

        y = (a*n+b)//m
        x = y*m-b

        if y==0:
            return ret

        ret += (n-(x+a-1)//a)*y
        n = y
        b = (a-x%a)%a
        m,a = a,m

T = int(input())

for i in range(T):
    n,m,a,b = list(map(int,input().split()))
    print(FloorSum(n,m,a,b))