龙之研习

题目描述

斯莫德，即涅卡里乌斯·吉刚塔烈诺·雷克·勒希帕斯·奥弗伦提斯，是知名竞技网游《英雄联盟》中第 167 位登场的英雄角色，常因出色的后期能力和可爱的幼龙外表活跃于官方赛事和同人作品中。在游戏里，斯莫德需要依靠他的被动技能，寻找机会叠加 “龙之研习” 层数，从而提升攻击属性。 最近，斯莫德穿过一道次元裂隙并降临到了现实世界，决定开始自己的叠层计划。起初斯莫德拥有 $0$ 个 “龙之研习” 层数。2024 往后的每一个平年，他都将通过训练获得 $1$ 个 “龙之研习” 层数；至于闰年，他只想休息玩乐，“龙之研习” 层数保持不变。

但千万不要以凡人的时间尺度来区分平年和闰年！作为帝巨龙，斯莫德的寿命是人类的亿亿倍，因此闰年规则必须作出调整：在 “四年一闰、百年不闰、四百年又闰” 的基础上，加入 “万年又不闰” 的限 制，然后 “四万年又又闰、百万年又又不闰……”。形式化地，年份 $n$ 是一个闰年，当且仅当存在唯一的非负整数 $p$ 使得 $n$ 整除 $4 × 100^p$ 但不整除 $100^{p+1}$，否则年份 $n$ 是一个平年。

那么问题来了，斯莫德将在哪一年叠到自己的第 $k$ 个 “龙之研习” 层数呢？请正确输出相应年份，不然斯莫德会从你身上索要 “龙之研习” 层数。

输入格式

本题单个测试点可能含有多组数据。输入的第一行包含数据组数 $T (1 ≤ T ≤ 10^5)$。 对于每组数据，在一行内读入一个整数 $k (1 ≤ k ≤ 10^{18})$，表示目标 “龙之研习” 层数。

输出格式

对于每组数据，在一行内输出一个整数，即叠到第 $k$ 个 “龙之研习” 层数的年份。

样例 #1

样例输入 #1

5
2
3
4
114514
998244353

样例输出 #1

2026
2027
2029
153181
1317684570