The strange life of a beehive Researchers recently discovered an interesting bee colony that lives in an 
infinite field of honeycomb:

  

Each cell can house a bee or not. In fact, the lives of those creatures 
appear to be a bit ... chaotic. It could be calculated that a colony 
always starts with the following pattern:

  

(Bee drawn by
Emmanuel Boutet 
on Wikimedia Commons. This 
honeycomb-and-bees image thus is released under
CC-By-SA. 
grumbles)

After that the bee's life cycles are divided into so-called generations. 
Each generation old bees die and new ones hatch and it primarily depends 
on their cell's neighbors:


If a bee has less than two neighbors it dies due to loneliness.
If a bee has more than three neighbors it dies due to overcrowding.
If a cell has two, three or four living bees in neighboring cells a new 
bee hatches there in the next generation.


Dying bees don't die until the end of a generation so they still affect 
surrounding cells that might hatch bees in the next generation.

Now that we know how such a colony works, we can simulate it through any 
number of generations.

Input

Input is a single number N, given on standard input, terminated by a line 
break. 0 ≤ N ≤ 150. This is the number of generations to simulate.

Output

Output is a single number, on standard output and optionally followed by a 
single line break, which represents the number of living bees after N 
generations.

Additional output on standard error is ignored.

Sample inputs

0
5
42
100


Sample outputs

6
44
1029
5296


Winning condition

Shortest code wins, as is customary in golf. In case of a tie, the earlier 
solution wins.

Test cases

There are two tests scripts, containing identical test cases:


bash
PowerShell


Invocation is in both cases: &lt;test script&gt; &lt;my program&gt; [arguments], 
e.g. ./test ruby beehive.rb or ./test.ps1 ./beehive.exe.

I know there are only 22 tests instead of 151 (mainly because solutions are often quite slow). Please refrain from 
embedding the exact test cases instead of solving the task. These scripts 
are a convenience for you to test whether a change still causes the 
program to behave correctly; not that you can adapt your code to the 
specific test cases.

Another note

This task was part of a golf contest held at my university during 
2011-W24. The scores and languages of our contestants were as follows:


336 – C
363 – C
387 – C
389 – Haskell
455 – C


Our own solution was


230 – Ruby
Ruby, 181 163 153 146 characters
h=[0]*4e4
[0,-200,201,202,2,3].map{|i|h[i]=1}
gets.to_i.times{h=h.map{[g=1,200,201].map{|x|g+=h[x]+h[-x]};g&gt;5-h.rotate![-1]||g&lt;3?0:1}}
p h.count 1

This implementation follows a standard approach using an array h (dimensions 200 x 200 flattened), where each element is either 0 (no bee) or 1 (bee included). The array [0,-200,201,202,2,3] describes the initial positions of bees (relative to any initial cell).
Input and output as specified above, passes all test cases defined.
Edit 1: changed back to a wrapping solution instead of the &quot;additional space&quot;-version (which was shorter in an intermediate version but now is several characters longer).
Edit 2: removed variable b completely.
Edit 3: warning: this edit made the program horribly slow. I thus reduced the dimensions to 200 each which still is sufficient for up to 150 iterations. Instead of indexing the array by a variable we constantly rotate the array forward. Not really good design, but now we are considerably below the 150.