该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

A sequence of grouped numbers is defined with the following pattern: the 1st group contains 1 number, which is $0\times 3+1$; the 2nd group contains 2 numbers, which are $0\times 3+2$ and $1\times 3+2$; the 3rd group contains 3 numbers, which are $1\times 3+3$, $2\times 3+3$ and $3\times 3+3$; and so on so forth. In general, the $i$-th group contains $i$ numbers, which starts from the last number of the previous group plus 1, and is incremented by 3 thereafter for each number. For example, the 3rd group can be explained as the following: it contains 3 numbers, which starts from the last number of the 2nd group (that is 5) plus 1 (which gives 6), and then obtain 9 by incrementing 6 by 3, and finally get 12 by incrementing 9 by 3.

So by definition, the first 10 numbers of this sequence are: 1, 2, 5, 6, 9, 12, 13, 16, 19, and 22. They actually consists of 4 groups: {1}, {2, 5}, {6, 9, 12} and {13, 16, 19, 22}.

Your job is to tell the index of any given number in this sequence.

输入格式

Each input file contains one test case. Each case starts from a positive integer $n$ ($\le 10^5$) in a line, which is the number of queries. Then $n$ lines follow, each contains a positive number that is no more than $10^5$.

输出格式

For each queried number, output in a line its index in the sequence (starting from 1). If the number is not in, output Not Found instead.

样例

4
12
16
5941
87654

6
8
2023
Not Found

限制

Java (javac) 时间限制 1000 ms 内存限制 512 MB

其他编译器 时间限制 400 ms 内存限制 64 MB