题目描述

wlx很喜欢在OW中选择SSVGG，但SSVGG玩家经常被嘲讽智商不高，wlx不认同这一点，于是便请教你完成下面的问题以证明SSVGG玩家的智商

如果一个奇数满足以下两个条件之一：

• 1.以5结尾
• 2.各个数位相加的和是3的倍数

则称它是一个"智数"

前5个"智数"分别为 { 3 , 5 , 9 , 15 , 21 }

现在wlx想要你给出升序排序下的第k个"智数"

输入描述

第一行输入一个正整数 T (1 ≤ T ≤ 10)，表示测试用例的组数

对于每组测试用例，在一行中输入一个正整数 k $(1 ≤ k ≤ 10^5)$

输出描述

对于每个问题，输出一行一个正整数，表示问题的答案

样例

示例1

输入

5
1
2
3
4
5

输出

3
5
9
15
21

示例2

输入

1
100000

输出

428571