Help Your Little Bunny

Little bunny just started going to school. Her mother left her at her school and went to her Office. As today is the first day of school there was only introduction class and after introducing with each other her class teacher wanted to know which subject is most favorite to all of her class. 99.99% of students voted for math in the class. Watching this her class teacher shared a story with her class obviously about math.

The story about a crazy mathematician Who loves to do her work using math. One day she was walking on a tiles floor. She noticed that She can go to her destination from the left bottom corner (0,0) to the right bottom corner(n,0) adding +1 to x-coordinate and (+1 or -1) to y-coordinate to her current position. She did that so many times and always thinks one can go from one place to another in the same flooring system.

After telling this story bunny's teacher told if you love mathematics you can see math everywhere.

The first Day of Bunny's school finished early. After leaving school, Bunny will walk to her mother. Bunny thought she would go to her mother like a mad mathematician and make her mother surprised (not using the normal road system).

Bunny thinks the Whole world is a 2D grid and her school at (0, 0) point, and her mother is at (n, 0) point. She starts going to her mother using the crazy mathematician method (+1 add to x-coordinate and ((+1 or -1 to y-coordinate)). Bunny can’t go out of the world(she’s a 2D grid system). Reaching her mother she told everything to her mother. Her Mother was a Math lover too, so she thinks there can be many ways Bunny can come to her. So she gives a task to Bunny to find out how many ways Bunny can come to her. But Bunny could not find any other such path to come to her mother.
You Love bunny so much you should help her.

You must solve this problem in this contest before helping your Bunny. You will be given TC times N the position of bunny's mother and find out the number of ways bunny can come to her mother if bunny can otherwise print "my Little Bunny is lost". Number of Ways can be very big you just print the ways module 1000000007(109 + 7).

See the sample test case for details.

Constraints

1 ≤ TC ≤ 100000

1 ≤ N ≤ 1000000

Input

The first line contains TC - the number of test case (1 ≤ TC ≤ 100000).

Next TC Lines contains an integer N(1 ≤ N ≤ 1000000)

Output

For every test case, you need to print “Case #T: ” (where T is the test case number) followed by number of ways or “my Little Bunny is lost”

Sample

Input	Output
2 2 1000000	Case #1: 1 Case #2: 213941567