Problem: linsane_phone_numbers (2012 finals)

As the Jeremy Lin sensation goes on, Roger, who is a geek and a super fan of
Jeremy Lin, decides his new cell phone number must be "Linsane". More
specifically, he wants his new phone number to satisfy:

1) Adjacent sum:  
There is at least one occurrence in the phone number of three adjacent digits
summing to **x**, where **x** is Lin's jersey number at New York Knicks.

2) Diversity:  
There are at least **y** different values of the digits used in the phone
number, where **y** is Lin's jersey number at Golden State Warriors.

3) Neighboring difference:  
There is at least one pair of neighboring digits whose difference is equal to
**z**, where **z** is Lin's jersey number at Harvard.

A phone number with length **n** contains **n** digits. Each digit is in the
range from 0 to 9, except that the first digit must be non-zero.  
A phone number is called "linsane" if it satisfies the three constraints
listed above.  
  
For phone numbers with a given length **n**, Roger wonders how many "linsane"
phone numbers exist.  
He also wants to find out the "most linsane" phone number among them.  
For a given length, the "most linsane" phone number is a "linsane" phone
number that has the biggest "linsanity measurement" among them.  
"Linsanity measurement" is defined as ![](http://rogeryu.com/Facebook_Hacker_C
up_2012_Final_Round_Problem_Linsanity.gif), where **n** is the number of
digits and **di** is the **i**-th digit in the phone number.  
If there is a tie on such measurement, choose the one whose median of the
digits is largest; and if there is still a tie, choose the largest phone
number.  
Median is the **(n+1)/2**-th smallest digit if **n** is odd, or the average of
the **(n/2)**-th and **(n/2+1)**-th digit if **n** is even. For example, the
linsanity measurement of number 78969251 is equal to (15*9)%8 + (17*6)%8 +
(15*9)%8 + (15*2)%8 +(11*5)%8 + (7*1)%8 = 40 with its median equal to 6.5.  

### Input

The first line contains a positive integer **T**, the number of test cases.
**T** test cases follow.

Each test case is a single line and contains exactly four integers separated
by single white space: **n x y z**, where **n** is the length of the phone
number, **x** is Lin's jersey number at New York Knicks, **y** is Lin's jersey
number at Golden State Warriors and **z** is Lin's jersey number at Harvard.  
(**x**,**y** and **z** are not necessarily 17, 7 and 4 in another parallel
universe.)

### Constraints

3 ≤ **n** ≤ 20  
0 ≤ **x** ≤ 27  
0 ≤ **y** ≤ 10  
0 ≤ **z** ≤ 9  
1 ≤ **T** ≤ 15  
Among the **T** test cases, there will be no more than 5 test cases with **n**
>12.

### Output

For each of the test cases numbered in order from **1** to **T**, output "Case
#", followed by the case number, followed by ": ", followed by the number of
possible "linsane" phone numbers _mod_ 1018 for the given length for that
case, and then a single space " " followed by the "most linsane" phone number
for the given length or -1 if no "linsane" phone number exists for the given
length.



Sample input:
5
6 17 7 4
7 17 7 4
8 17 7 4
9 10 5 2
20 15 10 1


Sample output:
Case #1: 0 -1
Case #2: 97682 9732485
Case #3: 3657799 78969251
Case #4: 231355703 435255828
Case #5: 230877663780393592 90299299274965943891