Adam was a brilliant athlete and won loads of medals throughout his life. As luck would have it all his generations would have exactly K children each. In the final days of Adam's life, a thought struck to him to pass on his medals to his future generations. The condition that he put forward for his children was that they were to keep none of the medals with themselves and pass the entire fortune to their next generation before their death. The trend should continue in the similar manner. Another constraint put forward was that the medals were distributed equally among all the siblings and there should be no more medals left behind. The passing of the family fortune continues as long as such a division can be possible. Find out the maximum no. of generations N!(factorial N) medals can be passed on to.
First line will contain a single integer t , the number of testcase.
Next t line will contain 2 integer N and K each separated by a space.
Ouput t lines each containing a single integer denoting the maximum no. of generation possible for corresponding test case
Input: 2 4 2 3 6 Output: 3 1
|Time Limit:||0.151176 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions