IITWPC4B - Maggu and Triangles

no tags 

Maggu has a wire of length n. He has to make triangles out of it such that the side lengths of each triangle are integers. He now wants to know the number of distinct (not congruent) triangles that he can create using the wire of length n. Note that he has to use all of the wire in making the triangle.

Input

First line contains T: number of test cases. (1 <= T <= 10^5)
For each test case, there is a single line containging an integer n (n >= 1 && n <= 10^9)

Output

Each test case output a single integer representing the number of triangles he can create.

Example

Input:
3
5
7
9 Output:
1
2
3

hide comments
sw2022: 2022-12-25 13:57:07

got green in one go!

kuchnahiaata: 2018-03-22 08:20:45

do not waste time!
use AlcuinsSequence

Liquid_Science: 2016-01-23 13:17:41

faltu question -_-

kp101110000: 2016-01-17 17:07:26

waste of time

Shashank Tiwari: 2015-12-23 23:18:23

Don't waste your time on this question. This is based on mathematical formula. Just google. You will only benefit if you delve into deriving it else waste of time. Make sure that formula has rounding function and not ceiling or floor.

Last edit: 2015-12-23 23:19:05
Siddharth Singh: 2015-12-10 14:49:22

Shantanu's Comment Really Helped :)

shantanu tripathi: 2015-08-31 21:33:13

http://mathworld.wolfram.com/AlcuinsSequence.html
read this to solve

sushilverma: 2015-03-24 18:40:17

why is it 3 for n=9

AlcatraZ: 2014-03-05 23:45:48

for n=5, the only valid triangle which can be formed is of sides 1,2,2. hence ans is 1. ;)

$iddharth prasad: 2014-02-06 08:59:53

@Ankush Jain ans for n=4 is 0


Added by:praveen123
Date:2014-01-31
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge