44. NTHU Coding Throne 2016 - D. Magic Matrix

0 Judge

Code: 0


Magic Matrix

題目敘述

We are going to introduce magic matrices. The size of a magic matrix is $1 \times N$. A magic matrix consists of at most two different elements that satisfy the following rules:

  • All the elements are the same integer, or

  • except that some elements equal zero, all the other elements are the same positive integer.

For example, if $N=3$, $[0,0,4]$, $[4,4,4]$, $[0,0,0]$ and $[2,0,2]$ are magic matrices while $[1,2,3]$, $[2,2,4]$ are not. The addition of two magic matrices is the same as normal matrix.

Now, given $N$, you may produce any magic matrices $M_1$, $M_2$, $M_3$, $\cdots$, $M_k$ as you need. What we want to do is to add all the $k$ magic matrices that produce a new matrix $[1,2,3,\cdots,N]$. We know that the easiest way is to set $k=N$ with $M_1 = [1,0,0,\cdots,0]$, $M_2 = [0,2,0,0,\cdots,0]$, ..., $M_N = [0,0,\cdots,0,N]$. But it clearly is not the best way since that would require a lot of calculation. It is your task to find the minimum number of $k$, such that $M_{1}+M_{2}+\cdots+M_{k}=[1,2,3,\cdots,N]$.

輸入說明

The first line of the input contains an integer $T$ ($1 \leq T \leq 1000$), the number of test cases. There is only one line of input per test case containing a single integer $N$ ($1 \leq N \leq 10^{8}$).

輸出說明

For each test case, output an integer, which denotes the minimum possible number of $k$ as described above, in a line.

範例輸入

3
2
3
4

範例輸出

2
2
3

提示

no


Judge Setting

run-time limit: 500 ms
memory limit: 262144 byte
測資數量: 0