Recamán's Sequence

Let's imagine a lake with an infinitely long line of lily pads on it, each with a sequential integer written on them starting with 0. Initially, each pad has a fly on it. When the frog arrives onto a lily pad with a fly he will immediately eat it, and flies will not reappear. On day 0 a frog sits upon the lily pad marked 0 and eats the fly there. At the beginning of each day, he will jump to another lily pad based upon the following rules:

• On day D, the frog's jump will cover a distance of D spaces.
• The frog first looks at the lily pads D sapces to the left and right, and jumps to one based on the following logic:
  • If the left lily pad does not exist (index below 0), he will jump to the right.
  • If only one lily pad still has a fly, he will jump to that one.
  • If both lily pads still have flies, he will jump to the left.
  • If neither lily pads still have a fly, he will jump to the right.

There exists no pad -1, so on day 1 the frog hops from pad 0 to pad 1 and eats the fly there. There exists no pad -1, so on day 2 the frog hops from pad 1 to pad 3 and eats the fly there. Pad 0 was already visited, so on day 3 the frog hops from pad 3 to pad 6 and eats the fly there. On day 4 the frog hops from pad 6 to pad 2 and eats the fly there.

For reference, here's the frog's position at the end of the first 30 days.

 Day │ Pad 
─────│─────
  0  │  0  
  1  │  1  
  2  │  3  
  3  │  6  
  4  │  2  
  5  │  7  
  6  │ 13  
  7  │ 20  
  8  │ 12  
  9  │ 21  
 10  │ 11  
 11  │ 22
 12  │ 10
 13  │ 23
 14  │  9
 15  │ 24
 16  │  8
 17  │ 25
 18  │ 43
 19  │ 62
 20  │ 42
 21  │ 63
 22  │ 41
 23  │ 18
 24  │ 42
 25  │ 17
 26  │ 43
 27  │ 16
 28  │ 44
 29  │ 15
 30  │ 45

However during this time the frog only ate 29 flies, having jumped onto lily pads without flies on days 24 and 26.

Problem Statement

Input Data
First line is Q, the quantity of testcases.
Q lines then follow, each with a single integer D.

Answer
Should be Q space-separated integers, corresponding to the total quantity of flies the frog has eaten by at the end of day D.

Example

input data:
5
10
100
1000
10000
100000

answer:
11 92 825 7741 74253