Xét các số nguyên dương có tổng các chữ số là số nguyên tố được sắp tăng dần như sau:
\(2, 3, 5, 7, 11, 12, 14, 16, 20, 21, 23, ...\)

Yêu cầu: Cho số 𝑘, hãy tìm số thứ 𝑘 trong dãy.

Input:

• Dòng đầu chứa số nguyên \(𝑇\) \((𝑇 \leq 20)\) là số bộ dữ liệu.
• \(𝑇\) dòng sau, mỗi dòng chứa một số nguyên \(𝑘\).

Output:

• Gồm \(𝑇\) dòng, mỗi dòng chứa một số nguyên là số thứ \(𝑘\) trong dãy tương ứng với dữ liệu vào.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(𝑘 \leq 10^5\).
• Subtask \(2\) (\(50\%\) số điểm): \(𝑘 \leq 10^{15}\).

Example

2
2
5

3
11