## BDOI16B - Beautiful Factorial Game

Beautiful Factorial Game

The statement of this problem is very simple. Given two number n and k, you need to find the maximum power of k (i.e. x) such that n! % k^x = 0. Here n! is the notation of n factorial. If you are not familiar with the notation,

n! = 1 * 2 * 3 * 4 * 5 * 6 ….. * n

Input:

First line of the input will contain an integer t (1 <= t <= 20) denoting the number of test case. The next t lines contain two integer number n and k as described above.

Constraints:

For easy version, 1 <= n <= 10, 2 <= k <= 10

For harder version, 1 <= n <= 100000000, 2 <= k <= 100000000

Output:

For each test case, print “Case t: x” where t is the test case number and x is the maximum power of k for which n! % k^x = 0.

 Sample Input Output of sample input 2 5 2 1000 2 Case 1: 3 Case 2: 994

Explanation of the sample:

In the first test case, n = 5 and k = 2. So, n! = 120.

n! % 2^0 = 0

n! % 2^1 = 0

n! % 2^2 = 0

n! % 2^3 = 0

n! % 2^4 = 8

n! % 2^5 = 24

n! % 2^6 = 56

n! % 2^7 = 120

So, the answer should be 3.

Problem Setter: Rakibul Islam cyclic_func: 2017-01-07 10:00:13 C.a Last edit: 2017-01-07 10:08:05 aman224: 2016-11-28 14:37:05 AC!!! Last edit: 2016-11-29 00:03:37 [Lakshman]: 2016-10-07 22:09:08 There is already a problem with better constraints http://www.spoj.com/problems/GCPC11A/ wisfaq: 2016-10-07 14:59:35 For easy version, 1 <= n <= 10, 2 <= k <= 10 For harder version, 1 <= n <= 100000000, 2 <= k <= 100000000 Which of the two do we have here? Sushovan Sen: 2016-10-06 20:42:18 Test cases are very weak. Please add some more.