n, 3n, 5n

Time limit2sMemory limit1024 MB

Summary

For each query i, find the i-th term of the lexicographically smallest increasing sequence where each positive integer n has exactly one of n, 3n, and 5n in the sequence.

Level: Medium6 of 10
Topics: Number theory, Greedy, Math
Solved: No attempts yet

Problem

An infinite increasing sequence $a_i$ of distinct positive integers is the lexicographically smallest sequence that satisfies the following property.

For every positive integer $n$ , exactly one of $n$ , $3n$ , and $5n$ appears in the sequence.

Given a positive integer $i$ , find the value of $a_i$ .

Input

The first line contains the number of test cases $T$ ( $1\le T\le 100\,000$ ). Each of the next $T$ lines contains one value of $i$ ( $1\le i\le 100\,000$ ).

Output

Print $T$ lines. For each $i$ , print $a_i$ on its own line.

Examples1

Example 1
Input
```
3
1
2
3
```
Expected output
```
1
2
4
```