Hard Divide and Conquer > Dynamic Programming

Hasan is a very busy young mathematician and unlike other people of his age, he doesn’t want to waste time playing FIFA. Galib considers hasan be his best buddy and always wants to play FIFA with him. Hasan is a kind hearted mathematician and doesn’t want to be too rude to Galib. So Hasan gives Galib a problem if he able to solve it successfully, then Hasan will play FIFA with him. Galib is very weak in counting so he asks for your help. Hasan gives Galib two integer number N and M. How many N digit numbers using digits of N Galib can make which are also divisible by M. One more thing is that it doesn’t have any leading zeros. Input: ------ The first line contains an integer T( 1<= T <= 25 ) which denotes the number of Test cases. T test cases follow . Each test case contains two integers number N and M. Output: ------- For each test case, print a line “Case x: y” where x is replaced by the test case number and y is the how many N digit numbers Galib can make which are divisible by M. Constraints: ------- 1 <= T <= 25 2 <= N <= 10^18 1 <= M <= 100 Sample Input ------------ 2 104 2 223 4 Sample Output ------------- Case 1: 3 Case 2: 1

Shakil Ahmed