행운의 승차권

소련에서 발행한 버스와 기차 승차권의 번호는 자릿수가 항상 짝수 2N이었다. 러시아와 카자흐스탄의 여러 지역에서는 지금도 이런 번호를 쓴다. 번호의 앞쪽 절반 N자리의 합이 뒤쪽 절반 N자리의 합과 같으면 그 승차권을 행운의 승차권이라고 부른다.

번호는 0부터 9까지의 숫자 2N개를 늘어놓은 문자열이고, 첫 자리가 0인 번호도 포함한다.

이런 승차권을 먹으면 좋은 일이 생긴다고 믿는 아이가 많다.

N이 주어지면 행운의 승차권이 몇 개인지 세어라.

첫 줄에 테스트 케이스의 개수 T가 주어진다. ($1 \le T \le 100$)

다음 T개의 줄에 정수 N이 한 줄에 하나씩 주어진다. 승차권 번호의 자릿수는 2N이다. ($1 \le N \le 500$)

각 테스트 케이스마다 한 줄에 Case #i: 를 먼저 출력하고, 이어서 자릿수가 2N인 행운의 승차권의 개수를 출력한다. i는 1부터 시작하는 테스트 케이스 번호이다. 개수가 금방 커지므로 1000000007 ($10^9 + 7$)로 나눈 나머지를 출력한다.