International Abbreviation Olympiad takes place annually starting from 1989. Each year the competition receives an abbreviation of form IAO'y, where y stands for some number of consequent last digits of the current year. Organizers always pick an abbreviation with non-empty string y that has never been used before. Among all such valid abbreviations they choose the shortest one and announce it to be the abbreviation of this year's competition.

For example, the first three Olympiads (years 1989, 1990 and 1991, respectively) received the abbreviations IAO'9, IAO'0 and IAO'1, while the competition in 2015 received an abbreviation IAO'15, as IAO'5 has been already used in 1995.

You are given a list of abbreviations. For each of them determine the year it stands for.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of abbreviations to process. 

Then n lines follow, each containing a single abbreviation. It's guaranteed that each abbreviation contains at most nine digits.


-----Output-----

For each abbreviation given in the input, find the year of the corresponding Olympiad.


-----Examples-----
Input
5
IAO'15
IAO'2015
IAO'1
IAO'9
IAO'0

Output
2015
12015
1991
1989
1990

Input
4
IAO'9
IAO'99
IAO'999
IAO'9999

Output
1989
1999
2999
9999

Difficulty: HARD
Tags: Mathematics

Greedy algorithms

Implementation

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
delims = [0, 1989, 1999, 2099, 3099, 13099, 113099, 1113099, 11113099, 111113099, 1111113099]
n = int(input())
for i in range(n):
	suf = input()[4:]
	min_val = delims[len(suf)]
	d = int(suf)
	while d < min_val:
		d += 10 ** len(suf)
	print(d)


cache = [1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1989]

def solve(n):
	global cache
	y = cache[int(n) % 10]
	for _steps in range(len(n) - 1):
		mod = 10 ** (_steps + 2)
		new_tail = int(n) % mod
		old_tail = y % mod
		if new_tail > old_tail:
			y = y // mod * mod + new_tail
		else:
			y = (y // mod + 1) * mod + new_tail
	return y
n = int(input())
for i in range(n):
	num = input().split("'")[1]
	print(solve(num))


import math

def find_year(iao):
	if len(iao) == 1:
		year = 1980 + int(iao)
		if year < 1989:
			year += 10
		return year
	else:
		pre_year = find_year(iao[1:])
		pre_year_str = list(str(pre_year))
		if len(iao) > len(pre_year_str):
			pre_year_str = ['0' for _ in range(len(iao) - len(pre_year_str))] + pre_year_str
		if int(iao[0]) <= int(pre_year_str[-len(iao)]):
			pre_year_str[-len(iao)] = iao[0]
			return int(int(''.join(pre_year_str)) + math.pow(10, len(iao)))
		else:
			pre_year_str[-len(iao)] = iao[0]
			return int(''.join(pre_year_str))

def solve():
	n = int(input())
	for _ in range(n):
		y = input()[4:]
		year = find_year(y)
		print(year)
solve()


def run(n):
	l = len(n) - 1
	b = 1989
	l = 10 ** l
	while l > 1:
		b += l
		l //= 10
	if b <= int(n):
		return n
	b = str(b)
	if len(b) == len(n):
		return '1' + n
	else:
		if b[-len(n):] <= n:
			return b[:-len(n)] + n
		return str(int(b[:-len(n)]) + 1) + n
n = int(input())
for i in range(n):
	print(run(input()[4:]))


for i in range(int(input())):
	t = input()[4:]
	q = int(t)
	d = 10 ** len(t)
	while q < 1988 + d // 9:
		q += d
	print(q)


tn = [0] * 10000
ts = [0] * 10000
a = 1989
tn[1] = 1989
ts[1] = 9
for i in range(1, 12):
	a = a + 10 ** i
	tn[i + 1] = a
	ts[i + 1] = int(str(a)[-i - 1:])
noc = int(input())
for fk in range(noc):
	a = input()[4:]
	temp = len(a)
	a = int(a)
	print((a - ts[temp]) % 10 ** temp + tn[temp])


from sys import stdin
n = int(stdin.readline().strip())
st = set()
dp = dict()
for i in range(n):
	s1 = stdin.readline().strip()
	s = s1[4:]
	for j in range(len(s) - 1, -1, -1):
		aux = s[j:]
		if aux not in dp:
			x = 10 ** len(aux)
			s2 = int(aux)
			while s2 < 1989 or s2 in st:
				s2 += x
			st.add(s2)
			dp.update({aux: s2})
	print(dp[s])


from __future__ import print_function
dic = {'9': '1989', '0': '1990', '1': '1991', '2': '1992', '3': '1993', '4': '1994', '5': '1995', '6': '1996', '7': '1997', '8': '1998'}

def get_year(s):
	length = len(s)
	if len(s) == 1:
		return dic[s]
	pos = [s]
	pre = 1
	if s[0] == '0' or len(s) < 4 or (len(s) == 4 and int(s) < 1989):
		pos = []
	count = 0
	while count < length:
		if int(str(pre) + s) >= 1989:
			pos.append(str(pre) + s)
			count += 1
		pre += 1
	for i in range(1, length):
		year = get_year(s[i:])
		try:
			pos.remove(year)
		except ValueError:
			pass
	return pos[0]
m = int(input())
for i in range(m):
	x = input()
	abb = x[4:]
	print(int(get_year(abb)))


a = [1989]
pow = [10]
for __ in range(9):
	a.append(a[len(a) - 1] + pow[len(pow) - 1])
	pow.append(pow[len(pow) - 1] * 10)
n = int(input())
for __ in range(n):
	s = input()
	s = s[4:]
	k = len(s) - 1
	tmp = int(s)
	fst = a[k] % pow[k]
	if tmp < fst:
		tmp += pow[k]
	print(a[k] + (tmp - fst))


T = int(input())
for _ in range(T):
	s = input()
	s = s[4:]
	l = len(s)
	s = int(s)
	x = 1988
	t = 1
	for i in range(l):
		y = s % (t * 10)
		z = x % (t * 10)
		while True:
			x = x + t
			z = x % (t * 10)
			if y == z:
				break
		t = t * 10
	print(x)


list_sep = [1998, 2098, 3098, 13098, 113098, 1113098, 11113098, 111113098, 1111113098]

def go(st):
	length = len(st)
	if length >= 4:
		if int(st) <= list_sep[length - 2]:
			print('1' + st)
		else:
			print(st)
	elif length == 3:
		if int(st) < 99:
			print('3' + st)
		else:
			print('2' + st)
	elif length == 2:
		if int(st) == 99:
			print('1999')
		else:
			print('20' + st)
	elif int(st) == 9:
		print('1989')
	else:
		print('199' + st)
n = int(input())
for i in range(n):
	go(input()[4:])


import sys
import math
import itertools as it
import operator as op
import fractions as fr
L = [1989]
d = 10
for i in range(9):
	L.append(L[-1] + d)
	d *= 10
n = int(sys.stdin.readline())
for _ in range(n):
	s = sys.stdin.readline().strip()
	d = s[s.index("'") + 1:]
	k = len(d)
	d = int(d)
	k10 = 10 ** k
	A = L[k - 1]
	B = A + k10 - 1
	r = 0
	if d < A % k10:
		r = B - (B % k10 - d)
	else:
		r = A + (d - A % k10)
	print(r)


n = int(input())
lst = []
for i in range(n):
	n = input()
	lst.append(n[4:])
for i in lst:
	l = len(i)
	i = int(i)
	g = 0
	p = 10
	c = 1
	while c < l:
		g += p
		p *= 10
		c += 1
	while i < 1989 + g:
		i += p
	print(i)


n = int(input())
M = 1989
for _ in range(n):
	(s, visited, p) = (str(input())[4:], set(), 10)
	answer = 0
	for i in range(len(s)):
		t = int(s[-i - 1:])
		answer = t
		while answer < M:
			answer += p
		while True:
			if answer not in visited:
				visited.add(answer)
				break
			answer += p
		p *= 10
	print(answer)


n = int(input())
for testCase in range(n):
	s = input()[4:].strip()
	n = int(s)
	year = 1989
	period = 1
	for i in range(len(s) - 1):
		period *= 10
		year += period
	cur_suff = int(str(year)[-len(s):])
	if cur_suff <= n:
		print(year + n - cur_suff)
	else:
		all9 = int('9' * len(s))
		year += all9 - cur_suff
		print(year + 1 + n)


def mp():
	return map(int, input().split())

def lt():
	return list(map(int, input().split()))

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)

def listring(l):
	return ' '.join([str(x) for x in l])

def printlist(l):
	print(' '.join([str(x) for x in l]))
for _ in range(it()):
	string = ip()
	string = string[4:]
	k = 1988
	for i in range(len(string) - 1, -1, -1):
		suffix = string[i:]
		t = len(suffix)
		k += 10 ** (t - 1)
		while not str(k).endswith(suffix):
			k += 10 ** (t - 1)
	pt(k)


n = int(input())
res = []
for i in range(n):
	line = input()
	year = 1989
	for u in range(len(line) - 1, 3, -1):
		a = line[u:]
		k = len(a)
		while year % 10 ** k != int(a):
			year = year + 10 ** (k - 1)
		year += 10 ** k
	res.append(year - 10 ** k)
for i in res:
	print(i)


def main():
	l = []
	for i in range(int(input())):
		(y, n, m) = (1989, 0, 1)
		for d in input()[-1:3:-1]:
			n += (ord(d) - 48) * m
			m *= 10
			t = n - y % m
			y += (m + t if t < 0 else t) + m
		l.append(y - m)
	print('\n'.join(map(str, l)))
main()


def solve():
	s = input().strip('\n')
	(_, year) = s.split("'")
	k = len(year)
	year = int(year)
	cover = 0
	base10 = 10
	for _ in range(k - 1):
		cover += base10
		base10 *= 10
	while year < 1989 + cover:
		year += base10
	print(year)
n = int(input())
for _ in range(n):
	solve()


a = [1989, 1999, 2099, 3099, 13099, 113099, 1113099, 11113099, 111113099, 1111113099]
n = int(input())
for i in range(n):
	s = input()[4:]
	p = len(s)
	st = 10 ** p
	(x, y) = (int(s), a[p - 1])
	while x < y:
		x += st
	print(x)


x = [0, 1989]
for i in range(1, 10):
	x.append(x[-1] + 10 ** i)
for i in range(int(input())):
	k = input().split("'")[1]
	lb = x[len(k):len(k) + 2]
	if int(k) < int(str(lb[0])[-len(k):]):
		print(str(lb[1] - 1)[:-len(str(k))] + k)
	else:
		print(str(lb[0] - 1)[:-len(str(k))] + k)


n = int(input())

def get_next(x, suffix):
	k = 10 ** (len(suffix) - 1)
	num = int(x) + k
	while not str(num).endswith(suffix):
		num += k
	return num
res = []
for i in range(n):
	s = input().split("'")[1]
	d = 1989 + (int(s[-1]) + 1) % 10
	for i in reversed(range(len(s) - 1)):
		suf = s[i:]
		d = get_next(d, suf)
	res.append(d)
for r in res:
	print(r)


n = int(input())
for i in range(0, n):
	s = input()
	j = s[4:]
	mi = 10 * (10 ** (len(j) - 1) - 1) / 9 + 1989
	v = int(j)
	fr = 0
	while int(str(fr) + j) < mi:
		fr += 1
	print(str(int(str(fr) + j)))


n = int(input())
for _ in range(n):
	s = input().rstrip()
	k = len(s) - 4
	r = int(s[4:])
	ans = None
	if k == 1:
		if r == 9:
			ans = 1989
		else:
			ans = 1990 + r
	elif k == 2:
		if r == 99:
			ans = 1999
		else:
			ans = 2000 + r
	elif k == 3:
		if r <= 98:
			ans = 3000 + r
		else:
			ans = 2000 + r
	else:
		t = int('1' * (k - 4) + '3098')
		if r <= t:
			ans = 10 ** k + r
		else:
			ans = r
	print(ans)


def solve(x):
	l = len(x)
	if l == 1:
		return '19' + ('8' if x == '9' else '9') + x
	if l == 2:
		return ('19' if x == '99' else '20') + x
	if l == 3:
		return ('3' if int(x) <= 98 else '2') + x
	if l >= 4:
		y = int((l - 4) * '1' + '3098')
		return ('1' if int(x) <= y else '') + x
n = int(input())
for i in range(n):
	k = input()[4:]
	print(solve(k))