VECTAR4 - Changus Final Battle

Try the tutorial version first :  Changus Big Battle :  http://www.spoj.com/problems/VECTAR2/

Changu is going to fight a battle. He is powerful but he has a few limitations. If he kills x enemies on a particular day, then he can only kill x-1 or x or x+1 enemies on the next day. And also, he can kill no more than 1 enemy on the last day of battle. Given N, the number of enemies he has to kill to end the battle, you have to calculate the minimum number of days required for Changu to finish the battle, keeping in mind his limitations. He starts on day 1 by x=1, i.e. killing one enemy.

Input

The first line contains an integer T denoting the number of test cases.

Each of the next T lines contain an integer N.

Output

T lines : Minimum number of days required for each test case.

Constraints

1 <= T <= 10^5

1 <= N <= 10^18

Example

Input:
3
4
1
9

Output:
3
1
5

Explanation

Case 1 : 1 + 2 + 1

Case 2 : 1

Case 3 : 1 + 2 + 3 + 2 + 1

 

Note: Test files have been updated. Solutions will be rejudged.


Added by:Piyush Kumar
Date:2016-06-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2016-06-22 07:05:10 Akshat Jain
really nice
2016-06-22 05:57:28 KD
nice one
AC in 2nd Go
2016-06-21 08:26:29 Sushovan Sen
O(1) works fine for all test cases.

Last edit: 2016-06-21 08:27:48
2016-06-21 08:11:31 [Lakshman]
There is something strange in input file, there is at least one N<=400000000 for which my O(1) solution is getting WA . So I used mix of both log(sqrt(n)) and O(1).

Re: Your all solutions look a bit too overworked. Look for a very simple O(1) solution:)

Last edit: 2016-06-21 08:34:56
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.