This day (7 February 2013) is my 19th birthday  So, I want to celebrate it on SPOJ by making this EASY puzzle problem.

This game/puzzle is about matches, given n matches, your task is to arrange the matches (not necessarily all) such that number of rectangle (any size) is maximum.

Input

First line there is an integer T ≤ 100 then T lines follow, each line contain an integer n < 1.000.000.000.

Output

For each test case, output required answer (maximum number of rectangles)

Example

Input:
5
3
4
8
12
15
Output:
0
1
3
9
12

Explanation

-->First test case: No rectangle can be formed with only 3 matches

-->Second test case: Only one rectangle can be formed with 4 matches

-->Third test case:

there are max 3 rectangles (2 size 1×1, 1 size 2×1) can be formed with number of matches ≤ 8, here is one of the matches formation:

-->Fourth test case:

there are max 9 rectangles (4 size 1×1, 2 size 2×1, 2 size 1×2, 1 size 2×2) can be formed with number of matches ≤ 12, here is one of the formation:

-->Fifth test case:

there are max 12 rectangles (5 size 1×1, 3 size 2×1, 1 size 3×1, 2 size 1×2, 1 size 2×2) can be formed with number of matches ≤ 15, here is one of the formation:

Information

Time limit≈150x my program speed, Enjoy this birthday party game, I set this problem such that semi naive solution will pass..

See also: Another problem added by Tjandra Satria Gunawan