SP411 NUMQDW - Number of quite different words

Let's consider the alphabet consisting of the first **c** roman uppercase letters, i.e. {A, B, C, D, E, F} if **c** is 6. We will call two words _quite different_, if there is no common subsequence of length more than one between those two words. For example ABC and CBA are quite different, but ABBA and CADDCAD aren't, because AA is a subsequence of both words. Given a word **w** you are to find the number of words of length **n** that are quite different from **w**.

The first line will contain the number of test cases (at most 20). Then there will be pairs of lines, the first one containing the numbers **n** (**n** will fit into a 32-bit signed integer and will be non-negative) and **c** (1

Print one line for each test case, consisting only of the number of words that are quite different from **w**. As this number can be quite large, you just have to output its remainder when dividing by 4242.