Smolder, also known as Smolder the Dragon, is a hero character from the popular competitive game League of Legends. Known for his late-game scaling and cute appearance, he is active in both official tournaments and fan works. In the game, Smolder needs to rely on his passive ability to find opportunities to stack "Dragon Practice" layers, thereby increasing his attack power.

Recently, Smolder traveled through a dimensional rift and arrived in the real world, deciding to start his own stacking plan. Initially, Smolder has 0 "Dragon Practice" layers. Starting from the year 2024, he will gain 1 "Dragon Practice" layer through training every year; as for leap years, he just wants to rest and play, so his "Dragon Practice" layer count remains unchanged.

However, do not use the mortal scale of years to distinguish between common years and leap years! As an emperor dragon, Smolder's lifespan is billions of times that of a human, so the rules for leap years must be adjusted: based on the "leap every four years, skip every hundred years, leap every four hundred years" rule, add the restriction of "skip every ten thousand years," and then "leap every forty thousand years, skip every million years...". Formally, a year $n$ is a leap year if and only if there exists a unique non-negative integer $p$ such that $n$ is divisible by $4 \times 100^p$ but not divisible by $100^{p+1}$; otherwise, the year $n$ is a common year.

The question is, in which year will Smolder stack his $k$-th "Dragon Practice" layer? Please output the corresponding year, otherwise Smolder will come to you to collect his "Dragon Practice" layers.

Input

The first line contains the number of test cases $T$ ($1 \le T \le 10^5$).

For each test case, read one integer $k$ ($1 \le k \le 10^{18}$) in a single line, representing the number of "Dragon Practice" layers.

Output

For each test case, output one integer in a single line, which is the year he stacks his $k$-th "Dragon Practice" layer.

Examples

Input 1

5
2
3
4
114514
998244353

Output 1

2026
2027
2029
153181
1317684570