A. Reserve the threetime limit per test: 1 secondmemory limi…

A. Reserve the threetime limit per test: 1 secondmemory limit per test: 256 megabytes The muse, the myth, the legend has said: “reserve the three”. From now on, Swifties do not speak numbers that are divisible by 3 or end with the digit 3. If you ask them to enumerate the first k numbers, they will say: 1, 2, 4, 5, 7, 8, 10, 11, 14, 16, … Help the Swifties! Write a program that finds the k-th element of this sequence so they know when to stop (the elements are numbered from 1). Input The first line contains one integer t (1≤t≤100) — the number of test cases. Then t test cases follow. Each test case consists of one line containing one integer k (1≤k≤1000). Output For each test case, output in a separate line one integer x — the k-th element of the sequence to be enumerated by the Swifties. Examples Input #1 Output #1 101234567891000 1245781011141666