Multiplying factors is one of the most tiresome jobs of algebra, so now you might want to take the help of computers to do that. In this problem you will have to deal with expression of the form (x+a1)(x+a2)(x+a3)...(x+an−1)(x+an), given the value of n. To be more specific for n = 2 you have to find the length of the output x2 +x(a1 +a2)+a1a2, for n = 3 you have to find the length of the output x3 + x2(a1 + a2 + a3) + x(a1a2 + a1a3 + a2a3) + a1a2a3 and so on. In plain text mode this type of strings can be outputted in three lines as: 1234567890123456789012345678901234567890//This is not output 32 x +x (a +a +a )+x(a a +a a +a a )+a a a 123 121323 123 So the length of the result is 40 when n = 3. As with growth of n the length grows very fast so you dont need to output the length but output modulo 10000 value of the length only. For your convenience you might want to notice that for n = 10 the initial part of the multiplication answer is: 10 9 8 x +x(a+a+a+a+a+a+a+a+a+a~)+x(aa+aa+aa+aa+aa+aa+aa+aa+aa )+... 1 2 3 4 5 6 7 8 9 10 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 Input The input file contains at most 6005 lines of inputs. Each line consists of a single integer n (0 < n ≤ 1000000000). Here n means the number of factors that are to be multiplied. Input is terminated by a line where the value of n is zero. This line should not be processed. Output For each line of input produce one line of output. If the length of the multiplied string is t then for each input you should output the serial of output followed by t%10000. Please note that you dont need to put any unnecessary brackets and also note that you dont need to output terms like x1. Show the power of x only when it is greater than 1. Sample Input 1 2 3 4 5 8 12 0
2/2 Sample Output Case 1: 4 Case 2: 16 Case 3: 40 Case 4: 92 Case 5: 208 Case 6: 2332 Case 7: 9439