SPOJ.com - Problem SEQ7

SEQ7 - Yet Another Sequence Problem

no tags

We have an infinite non-decreasing sequence A which is created as follows:

A[1] = 1 and A[2] = 2.
A number i occurs A[i] times in the sequence.

First few terms in the sequence are: { 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7... }. Note that 3 occurs 2 times in the sequence, (because A[3] = 2).

Your task is to find the term A[n] for any given n, where 0 < n <= 1e13.

Input

First line contains t, the number of test cases. Each of the next t lines contains a number n.

Output

For every case, print the nth term of the sequence.

Example

Input:
2
5
12

Output:
3
6

Submit solution!

hide comments



	Soma: 2015-06-24 03:17:12 @sivanatarajan : write a brute force program in python and cross check with your output(from one which implements your algorithm).
	sivanatarajan: 2014-10-21 19:08:57 anyone tell some more test cases..
	Pranjal Successena: 2013-04-22 21:28:21 can u chk my code? I jst don't know y its gving "run time error".. 91440088
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-01-05 12:30:38 what is this? just use approximation and got AC in 0.00s (without fast I/O) I haven't optimize my code, but seems that my algo is fastest compared to other ;-) plus I only use 1,7MB of memory...
	sandeep pandey: 2012-03-16 08:40:45 Binary Search will be okay :\| Last edit: 2012-09-18 17:53:56
	Ashish Sahay: 2011-12-18 11:04:42 is the answer for 1e13-130097223???
	:D: 2011-06-23 11:51:09 No, basic arithmetic's is enough.
	uevoliinilas: 2011-05-12 10:55:02 Is this same as http://acm.mipt.ru/judge/problems.pl?problem=047&CGISESSID=12027e31a8c0844fbf3fadfa731bbb29 or here we have to use any advanced matrix exponentiation ?
	Piotr KÄ…kol: 2011-05-10 11:46:27 Is the answer for 1e13 - 130097224? Edit : No. Last edit: 2011-05-10 12:23:01
	Gabriel: 2011-05-09 18:44:54 My Python code gets the correct answer for n up to 10^13 (I checked it with Mathematica), but still I'm getting wrong answer here... Edit: Did you try with a brute force checker ? The formula you are using has an error term associated with it. Last edit: 2011-05-10 05:04:55

Submit solution!

Added by:	Paranoid Android
Date:	2011-05-09
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64