Medium Math > Combinations and Permutations

In the land of Middle Earth, there lived a frightening “mathological” creature. It asked people a hard math problem and if people were not able to answer correctly, they were eaten alive. It asked people the following math problem: Count the number of ways to distribute **N** unique items to **M** people so that each people gets same number ( **N/M** ) of items where N is **multiple** of M. Giving the solution modulo some huge prime number was enough to survive. With the passage of time the fear of the creature declined. People were easily be able to answer the question. So the creature decided to adapt, he started asking the number of digits of the solution. The people were faced with a new threat as they were not able to answer the question. So they came to you, the famous “Mathrandir”. Can you answer the questions and save all the people? Input: ------ First line gives number of test cases (T). T lines follow, each containing N and M. Output: ------- For each test case print the number of digits of the actual solution to the problem. Limits: ------- T<=10000 M<=N<=100000 N is multiple of M Sample Input ------------ 2 4 4 10 5 Sample Output ------------- 2 6 Explanation ------------ There are 24 ways to distribute 4 items among 4 people. So number of digits is 2. Similarly, there are 113400 ways in second test case. So answer is 6.

Sheikh Moinul Hasan