The Chef commutes to work every day using the city's underground metro. The schedule for the trains has recently been changed and he wants to know how long it will take to travel from the station nearest to his house and the station nearest to his restaurant.

The Chef doesn't want to change the route he took before, so he simply has to find out how long it will take to reach his restaurant along his usual route. This route is given by a sequence of stations s_{0}, s_{1}, ..., s_{n} where s_{0} is the station where the Chef enters the metro and s_{n} is the station where the Chef exits the metro.

Trains are scheduled to run between every two consecutive stations s_{i-1} and s_{i}. Such a schedule is specified by three integers x_{i}, l_{i}, and f_{i}. This means that the first train on this line starts operating at time x_{i}. The time it takes this train to travel from s_{i-1} and s_{i} is exactly l_{i} units. Finally, a train departs from station s_{i-1} every f_{i} minutes following the previous train. That is, a train departs at time x_{i}, x_{i}+f_{i}, x_{i}+2f_{i}, and so on.

The Chef is very experienced at navigating the metro so the time it takes him to transfer between trains at a given station  is essentially zero. Thus, if the Chef arrives at a station, say s_{i}, the moment that the train from s_{i} to s_{i+1} is scheduled to depart, he skillfully hops on this next train. However, if the Chef arrives when no train to s_{i+1} is scheduled to depart, he must wait until the scheduled departure time.

Help the Chef figure out how long it will take him to travel from station s_{0} to station s_{n}. You may assume that the Chef is already at station s_{0} at time 0.

------ Input ------ 

The first line consists of a single integer denoting the number of test cases (at most 50). Each test case begins with a line containing a single integer n between 1 and 1000 indicating the number of lines the Chef must traverse (so there are n+1 stations s_{0}, s_{1}, ..., s_{n}). The next n lines describe the train schedules between stations, one per line. The i'th such line gives the values x_{i}, l_{i}, and f_{i} for the train that travels between stations s_{i-1} and s_{i}.

The x_{i} values will be between 0 and 1000 and the l_{i} and f_{i} values will be between 1 and 1000.

------ Output ------ 

For each test case you are to output a single integer denoting the minimum time t for which the Chef can reach station s_{n} using the given route. Remember, the Chef starts at s_{0} at time 0.

----- Sample Input 1 ------ 
3
2
0 4 7
0 6 5
2
0 1 2
6 2 10
2
1 2 3
0 2 3
----- Sample Output 1 ------ 
11
8
5

Difficulty: EASY
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(n):
		(x, l, f) = map(int, input().split())
		if ans <= x:
			ans += x - ans
		else:
			m = (ans - x) % f
			if m != 0:
				ans += f - m
		ans += l
	print(ans)


for _ in range(int(input())):
	n = int(input())
	curr_time = 0
	for i in range(n):
		(x, l, f) = map(int, input().split())
		while x < curr_time:
			x += f
		curr_time += x - curr_time
		curr_time += l
	print(curr_time)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	s = []
	for j in range(n):
		l = list(map(int, input().split()))
		s.append(l)
	c = s[0][0] + s[0][1]
	for k in range(1, len(s)):
		if c < s[k][0]:
			c += s[k][0] - c + s[k][1]
		elif c == s[k][0]:
			c += s[k][1]
		elif (c - s[k][0]) % s[k][2] == 0:
			c += s[k][1]
		else:
			a = (c - s[k][0]) % s[k][2]
			c += s[k][2] - a + s[k][1]
	ans.append(c)
for z in ans:
	print(z)


t = int(input())
for k in range(t):
	n = int(input())
	a = 0
	for i in range(n):
		(x, l, f) = list(map(int, input().split()))
		while a > x:
			x += f
		a = x + l
	print(a)


import math as m
for _ in range(int(input())):
	a = list()
	N = int(input())
	for i in range(N):
		input_list = list(map(int, input().split()))
		a.append(input_list)
	time = 0
	for i in range(N):
		if i == 0:
			time += a[i][0] + a[i][1]
		elif a[i][0] >= time:
			time += a[i][0] - time
			time += a[i][1]
		else:
			time += a[i][0] + m.ceil((time - a[i][0]) / a[i][2]) * a[i][2] - time + a[i][1]
	print(time)


import math
for t in range(int(input())):
	n = int(input())
	t = 0
	for i in range(n):
		xlf = [int(j) for j in input().split(' ')]
		if xlf[0] >= t:
			t = xlf[0]
		else:
			i = 0
			while xlf[0] + xlf[2] * i < t:
				i += 1
			t = xlf[2] * i + xlf[0]
		t = t + xlf[1]
	print(t)


for tc in range(int(input())):
	n = int(input())
	curtime = 0
	for i in range(n):
		(x, l, f) = map(int, input().split())
		leavetime = x
		while curtime > leavetime:
			leavetime = leavetime + f
		curtime = leavetime + l
	print(curtime)


for _ in range(int(input())):
	n = int(input())
	c = 0
	for i in range(n):
		(x, l, f) = map(int, input().split())
		if c <= x:
			c += x - c
		else:
			a = (c - x) % f
			if a != 0:
				c += f - a
		c += l
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	time = 0
	for i in l:
		if i[0] >= time:
			time = i[0] + i[1]
		else:
			x = 0
			if (time - i[0]) // i[2] == (time - i[0]) / i[2]:
				time += i[1]
			else:
				time += ((time - i[0]) // i[2] + 1) * i[2] - (time - i[0]) + i[1]
	print(time)


o = int(input())
for i in range(o):
	s = int(input())
	t = 0
	for j in range(s):
		(l, m, n) = map(int, input().split())
		if t <= l:
			t += l - t
		else:
			p = (t - l) % n
			if p != 0:
				t += n - p
		t += m
	print(t)


from itertools import count
for i in range(int(input())):
	k = int(input())
	chef_time = 0
	for station in range(k):
		(x, l, f) = map(int, input().split())
		if station == 0:
			chef_time += x + l
		else:
			for c in count(x, f):
				if c >= chef_time:
					chef_time = c + l
					break
	print(chef_time)


for _ in range(int(input())):
	N = int(input())
	array = []
	for i in range(N):
		array.append(list(map(int, input().split())))
	time = 0
	for i in range(N):
		p = array[i]
		if (time - p[0]) % p[2] == 0 and time - p[0] >= 0:
			time += p[1]
		elif time < p[0]:
			time = p[0] + p[1]
		else:
			k = (p[0] - time) % p[2]
			time += k + p[1]
	print(time)


t = input()
for c in range(0, int(t)):
	n = int(input())
	time = 0
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	for j in range(n):
		next_train = a[j][0]
		while next_train < time:
			next_train += a[j][2]
		time += next_train + a[j][1] - time
	print(time)


from math import floor
t = int(input())
for ni in range(t):
	n = int(input())
	t = 0
	for nj in range(n):
		(x, l, f) = map(int, input().split())
		if t < x:
			t = x + l
		elif (t - x) % f == 0:
			t = t + l
		else:
			t = t + f - (t - x) % f + l
	print(t)


import sys
import math

def main(arr):
	time_passed = 0
	for e in arr:
		(x, l, f) = e
		temp = (time_passed - x) / f
		if temp < 0:
			time_passed += x - time_passed
		else:
			time_passed += math.ceil(temp) * f + x - time_passed
		time_passed += l
	return time_passed
for i in range(int(input())):
	n = int(input())
	stations = []
	for i in range(n):
		stations.append(list(map(int, input().split())))
	print(main(stations))


t = int(input())
while t:
	n = int(input())
	c = 0
	for i in range(n):
		(x, l, f) = map(int, input().split())
		if i == 0:
			c += x + l
			continue
		if (c - x) % f:
			c += f + l - (c - x) % f
		else:
			c += l
	print(c)
	t -= 1


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	t = 0
	for i in range(n):
		(x, l, f) = map(int, stdin.readline().split())
		if t <= x:
			t = x
		elif (t - x) % f != 0:
			t += f - (t - x) % f
		t += l
	print(t)


test = int(input())
for _ in range(test):
	n = int(input())
	time = []
	for i in range(n):
		temp = list(map(int, input().split()))
		time.append(temp)
	duration = 0
	for i in range(n):
		temp = time[i]
		start = temp[0]
		total = temp[1]
		freq = temp[2]
		if duration <= start:
			wait = start - duration
		elif (duration - start) % freq == 0:
			wait = 0
		else:
			wait = freq - (duration - start) % freq
		duration = duration + total + wait
	print(duration)


test = int(input())
for _ in range(test):
	n = int(input())
	ans = 0
	for i in range(n):
		(x, l, f) = list(map(int, input().split()))
		while ans > x:
			x += f
		ans = x + l
	print(ans)


for _ in range(int(input())):
	n = int(input())
	time = 0
	for i in range(n):
		(x1, l1, f1) = map(int, input().split())
		if x1 < time:
			p = (time - x1) % f1
			if p != 0:
				time = time + (f1 - p) + l1
			else:
				time = time + l1
		elif x1 > time:
			time = time + l1 + abs(time - x1)
		else:
			time = time + l1
	print(time)


for _ in range(int(input())):
	n = int(input())
	t = 0
	for i in range(n):
		(x, l, f) = map(int, input().split())
		lt = x
		while t > lt:
			lt = lt + f
		t = lt + l
	print(t)


t = int(input())
for i in range(t):
	n = int(input())
	ans = 0
	for j in range(n):
		(x, l, f) = map(int, input().split())
		if j == 0:
			ans = x + l
		elif ans <= x:
			ans += abs(x - ans)
			ans += l
		else:
			z = (ans - x) / f + 1
			if int(z) == z:
				ans += x + (int(z) - 1) * f - ans
				ans += l
			else:
				ans += x + int(z) * f - ans
				ans += l
	print(int(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for _ in range(n):
		temp = tuple(map(int, input().split()))
		arr.append(temp)
	tot_time = arr[0][0] + arr[0][1]
	for i in range(1, n):
		if arr[i][0] >= tot_time:
			tot_time = arr[i][0] + arr[i][1]
		else:
			f = (tot_time - arr[i][0]) // arr[i][2]
			rem = (tot_time - arr[i][0]) % arr[i][2]
			if rem == 0:
				tot_time = arr[i][0] + f * arr[i][2] + arr[i][1]
			else:
				tot_time = arr[i][0] + (f + 1) * arr[i][2] + arr[i][1]
	print(tot_time)


for i in range(int(input())):
	lines = int(input())
	time = 0
	for j in range(lines):
		(x, l, f) = map(int, input().split())
		if time <= x:
			time += x - time
		else:
			mod = (time - x) % f
			if mod != 0:
				time += f - mod
		time += l
	print(time)


for _ in range(int(input())):
	stations = int(input())
	detail = []
	for _ in range(stations):
		(start, travel, freq) = map(int, input().split())
		detail.append([start, travel, freq])
	(start, travel, freq) = detail.pop(0)
	curTime = start + travel
	for (start, travel, freq) in detail:
		curTime += (freq - (curTime % freq - start)) % freq
		curTime += travel
	print(curTime)


t = int(input())
for tc in range(t):
	n = int(input())
	d = 0
	for j in range(n):
		(x, l, f) = map(int, input().split())
		s = x
		while d > s:
			s += f
		d = s + l
	print(d)


t = int(input())
for h in range(t):
	n = int(input())
	du = 0
	for r in range(n):
		(x, l, f) = list(map(int, input().split()))
		while du > x:
			x = x + f
		du = x + l
	print(du)


import math
for _ in range(int(input())):
	N = int(input())
	(x0, l0, f0) = map(int, input().split())
	commute = x0 + l0
	for __ in range(1, N):
		(x1, l1, f1) = map(int, input().split())
		intervals = max(0, math.ceil((commute - x1) / f1))
		wait = (x1 + f1 * intervals) * (x1 < commute) + x1 * (x1 > commute)
		commute = wait + l1
		(x0, l0, f0) = (x1, l1, f1)
	print(commute)


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = []
	for _ in range(n):
		temp = list(map(int, input().strip().split()))
		list1.append(temp)
	time = 0
	for val in list1:
		start = val[0]
		duration = val[1]
		interval = val[2]
		if time <= start:
			wait = start - time
		elif (time - start) % interval == 0:
			wait = 0
		else:
			wait = interval - (time - start) % interval
		time += wait + duration
	print(time)


import math
for _ in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(n):
		(x, l, f) = map(int, input().split())
		if ans <= x:
			ans = x
			ans += l
		else:
			t_1 = math.ceil((ans - x) / f)
			t_1 = t_1 * f + x
			t_2 = t_1 - ans
			ans += t_2
			ans += l
	print(ans)


from math import ceil
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	X = []
	L = []
	F = []
	for i in range(N):
		(x, l, f) = [int(i) for i in input().split()]
		X.append(x)
		L.append(l)
		F.append(f)
	time = 0
	for i in range(0, N):
		K = max(ceil((time - X[i]) / F[i]), 0)
		time += X[i] + K * F[i] - time + L[i]
	ans.append(time)
for i in ans:
	print(i)


import sys
import math
import bisect

def main():
	for _ in range(int(input())):
		n = int(input())
		t = 0
		for i in range(n):
			A = list(map(int, input().split()))
			if t < A[0]:
				t = A[0] + A[1]
			else:
				t = A[0] + (t - A[0] + A[2] - 1) // A[2] * A[2]
				t += A[1]
		print(t)
main()


for _ in range(int(input())):
	n = int(input())
	t = 0
	for __ in range(n):
		(x, l, f) = map(int, input().split())
		if t < x:
			t = x
		if (t - x) % f:
			t += f - (t - x) % f
		t += l
	print(t)


import math
for i in range(int(input())):
	t = 0
	n = int(input())
	for x in range(n):
		(a, b, c) = map(int, input().split())
		if x == 0:
			t += a + b
		elif t - a == 0:
			t += b
		elif t < a:
			t += a - t + b
		else:
			t += a + math.ceil((t - a) / c) * c - t + b
	print(t)


for _ in range(int(input())):
	list1 = (map(int, input().split()) for _ in range(int(input())))
	time = 0
	for (x, l, f) in list1:
		if x < time:
			time = time if (time - x) % f == 0 else x + ((time - x) // f + 1) * f
		else:
			time = x
		time += l
	print(time)


def solve():
	n = int(input())
	a = 0
	for i in range(n):
		(x, l, f) = list(map(int, input().split()))
		while a > x:
			x += f
		a = x + l
	print(a)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	x = []
	l = []
	f = []
	for i in range(n):
		(a, b, c) = map(int, input().strip().split())
		x.append(a)
		l.append(b)
		f.append(c)
	time = 0
	for i in range(n):
		if i == 0:
			time = x[0] + l[0]
		elif time < x[i]:
			time = time + (x[i] - time) + l[i]
		elif time == x[i]:
			time = time + l[i]
		else:
			time = time + (x[i] - time) % f[i] + l[i]
	print(time)


class Line:

	def __init__(self, start, ttime, nextDep):
		self.start = start
		self.ttime = ttime
		self.nextDep = nextDep

	def travel(self, t):
		tDep = self.start
		while True:
			if t <= tDep:
				return tDep + self.ttime
			tDep += self.nextDep
TC = int(input())
for _ in range(TC):
	N = int(input().strip())
	lines = []
	for _ in range(N):
		(x, l, f) = list(map(int, input().strip().split()))
		lines.append(Line(x, l, f))
	t = 0
	for line in lines:
		t = line.travel(t)
	print(t)


for _ in range(int(input())):
	n = int(input())
	starting = []
	timeTaken = []
	succession = []
	for _ in range(n):
		(temp1, temp2, temp3) = input().split()
		starting.append(int(temp1))
		timeTaken.append(int(temp2))
		succession.append(int(temp3))
	totalTime = 0
	for i in range(n):
		if i == 0:
			totalTime += starting[i] + timeTaken[i]
		elif totalTime < starting[i]:
			totalTime = starting[i] + timeTaken[i]
		elif totalTime >= starting[i]:
			temp = starting[i]
			while totalTime > temp:
				temp += succession[i]
			totalTime = temp + timeTaken[i]
	print(totalTime)


T = int(input())
for _ in range(T):
	n = int(input())
	ans = 0
	for i in range(n):
		(a, b, c) = map(int, input().split())
		if ans <= a:
			ans = a + b
		else:
			d = ans
			ans = a
			while ans < d:
				ans += c
			ans += b
	print(ans)


for i in range(int(input())):
	n = int(input())
	t = 0
	for i in range(n):
		(x, l, f) = map(int, input().split())
		if t <= x:
			wait = x - t
		elif (t - x) % f == 0:
			wait = 0
		else:
			wait = f - (t - x) % f
		t = t + wait + l
	print(t)


import math
for _ in range(int(input())):
	n = int(input())
	arr = [[0 for i in range(3)] for j in range(n)]
	for i in range(n):
		(arr[i][0], arr[i][1], arr[i][2]) = map(int, input().split())
	time = 0
	for i in range(n):
		if time > arr[i][0]:
			k = math.ceil((time - arr[i][0]) / arr[i][2])
			time = arr[i][0] + k * arr[i][2] + arr[i][1]
		else:
			time = arr[i][0] + arr[i][1]
	print(time)


z = int(input())
for _ in range(z):
	n = int(input())
	s = []
	for i in range(n):
		s.append(list(map(int, input().split())))
	t = 0
	for i in range(n):
		st = s[i]
		while st[0] < t:
			st[0] += st[2]
		t = st[0]
		t += st[1]
	print(t)


T = int(input())

def algo():
	t = 0
	n = int(input())
	for i in range(n):
		(st, dt, f) = map(int, input().split())
		ct = st
		while t > ct:
			ct += f
		t = ct + dt
	print(t)
for i in range(T):
	algo()


for _ in range(int(input())):
	N = int(input())
	commuteTime = 0
	for s in range(N):
		(X, L, F) = map(int, input().split())
		wait = 0
		travel = L
		if s == 0:
			wait = X
		else:
			t1 = (commuteTime - X) // F
			mod = (commuteTime - X) % F
			if mod != 0:
				t1 += 1
			nextTrain = X + t1 * F
			wait = nextTrain - commuteTime
		commuteTime += wait + travel
	print(commuteTime)


for _ in range(int(input())):
	n = int(input())
	time = 0
	for _ in range(n):
		(x, l, f) = map(int, input().split())
		if time < x:
			time = x + l
		elif (time - x) % f == 0:
			time += l
		else:
			time += f - (time - x) % f + l
	print(time)


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	schedule = []
	for i in range(n):
		l = list(map(int, input().split()))
		schedule.append(l)
	time = schedule[0][0] + schedule[0][1]
	for i in range(1, len(schedule)):
		if time < schedule[i][0]:
			time += schedule[i][0] - time + schedule[i][1]
		elif time == schedule[i][0]:
			time += schedule[i][1]
		elif (time - schedule[i][0]) % schedule[i][2] == 0:
			time += schedule[i][1]
		else:
			wait = (time - schedule[i][0]) % schedule[i][2]
			time += schedule[i][2] - wait + schedule[i][1]
	ans.append(time)
for _ in ans:
	print(_)