C Programming Language

Material: Sorting and Searching (Use Quick Sort)

Problem Title: Magic Potion Jojo is the best chemist in the city. One day, a customer ask Jojo to create a magic potion. After days of research, Jojo finally found formula for magic potion. A magic potion can be created by combining exactly one bottle of potion A, exactly one bottle of potion B, and exactly one bottle of potion C regardless the composition ratio. So, if Jojo has X liter bottle of potion A, Y liter bottle of potion B, and Z liter bottle of potion C, once he combines it, he has to use the entire bottle and he will get X + Y + Z liter of magic potion.

One day, a customer ask for K liter of magic potion. Jojo immediately look at his shelves of potion. At shelf A, he has NA bottles of potion A (each bottle has different capacity). The i-th bottle of potion A has Ai liter capacity. At shelf B, he has NB bottles of potion B (each bottle has different capacity). The i-th bottle of potion B has Bi liter capacity. At shelf C, he has NC bottles of potion C (each bottle has different capacity). The i-th bottle of potion C has Ci liter capacity. Jojo wants to know how many ways he can create K liter of magic potion. Remember that He Can ONLY use Exactly ONE bottle and use the Entire Bottle of Each Potion Type.

Format Input

There are T testcases. Every testcase consists of a line of an integer NA followed by a line of NA integers A1, A2, ..., A_NA. Followed by a line of an integer NB followed by a line of NB integers B1, B2, ..., B_NB. Followed by a line of an integer NC followed by a line of NC integers C1, C2, ..., C_NC . And finally followed by a line consists of an integer K.

Format Output

Output T testcases with format Case #X: , where X indicates the testcase number and then followed by an integer indicates how many ways Jojo can create K liter of magic potion.

Constraints

1 T 5 1 N_A, N_B, N_C 1000 1 A_i, B_i, C_i, K 1000000000

Sample Input (standard input)

3 3 1 2 3 3 3 2 1 3 5 1 3 7

5 1 3 7 10 9 4 2 5 12 8 3 13 23 22 100

3 2 3 5 3 3 5 2 3 5 2 3 10

Sample Output (standard output)

Case #1: 5

Case #2: 0

Case #3: 6

NOTE :

Read The Question Carefully

Input And Output Must Be The Same