Some engineers got tired of dealing with all the different ways of encoding status messages, so they decided to invent their own. In their new scheme, an encoded status message consists of a sequence of integers representing the characters in the message, separated by spaces. Each integer is between \textbf{1} and \textbf{M}, inclusive. Unfortunately they decided to compress the encoded status messages by removing all the spaces! Your task is to figure out how many different encoded status messages a given compressed status message could have originally been. Because this number can be very large, you should return the answer modulo \textbf{4207849484 }(\textbf{0xfaceb00c} in hex). For example, if the compressed status message is "\textbf{12}" it might have originally been "\textbf{1 2}", or it might have originally been "\textbf{12}". The compressed status messages are between \textbf{1} and \textbf{1000} characters long, inclusive. \InputFile The input begins with a single integer, \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{25}), the number of compressed status messages you must analyze. This will be followed by \textbf{N} compressed status messages, each consisting of an integer \textbf{M} (\textbf{2} ≤ \textbf{M} ≤ \textbf{255}), the highest character code for that database, then the compressed status message. All tokens in the input will be separated by some whitespace. It is known that \textbf{1} ≤ length of encoded status ≤ \textbf{1000}. \OutputFile For each of the test cases numbered in order from \textbf{1} to \textbf{N}, output "\textbf{Case #i:} " followed by a single integer containing the number of different encoded status messages that could be represented by the corresponding compressed sequence. If none are possible, output a \textbf{0}.