## MBEEWALK - Bee Walk

English | Vietnamese |

A bee larva living in a hexagonal cell of a large honey comb decides to creep for a walk. In each “step” the larva may move into any of the six adjacent cells and after n steps, it is to end up in its original cell. Your program has to compute, for a given n, the number of different such larva walks.

### Input

The ﬁrst line contains an integer giving the number of test cases to follow. Each case consists of one line containing an integer n, where 1 ≤ n ≤ 14. SAMPLE INPUT 2 2 4

### Output

For each test case, output one line containing the number of walks. Under the assumption 1 ≤ n ≤ 14, the answer will be less than 2^31. SAMPLE OUTPUT 6 90

Added by: | ~!(*(@*!@^& |

Date: | 2009-02-24 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM qobi SCM guile ST WHITESPACE |