## JZPCIR - Jumping Zippy

Jumping Zippy likes to jump. He jumps every day and feels boring. Then he think of a new way to jump. He jumps on a big round plaza. The plaza is divided into n sectors numbered clockwise from 0 to n-1. Firstly, he stands on sector 0. Each time, when he is stand on sector x, he can jump to sector (x-2)%n, (x-1)%n, (x+1)%n or (x+2)%n. His goal is to jump to each sector exactly once and jump back to sector 0 at last. And for the first jump, he never jumps to sector n-1 or sector n-2. He wants to find the number of different ways in which he can complete his goal.

### Input

First line is a number t, which is the number of testcases. (1<=t<=1000)

Then following t lines, each line contains a integer n, which is the number of sectors. (5<=n<=10^18)

** **

**Output**

For each query n, output a line which contains one integer, the number of different ways Zippy can complete his goal in, modulo 10^9+9.

### Example

Input:5 5 6 7 8 9Output:12 16 23 29 41

Added by: | sevenkplus |

Date: | 2010-10-29 |

Time limit: | 0.577s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | own problem |