BBAD  Breaking Math
The worst of them is Heisenburg, a badass physicist and the ultimate drug lord. Walter needs Heisenburg’s active support to distribute the methamphetamine he produces. Alas, Heisenburg is a cautious man. Heisenburg is initially skeptical about Walter, and decides to give the following problem to Walter in order to prove his worth.
w(n) is defined to be the number of distinct prime factors of n, for example:
w(1) = 0, w(2) = 1, w(3) = 1, w(4) = 1, w(5) = 1, w(6) = 2, w(30) = 3
f(n, k) = ∑ k^{w(i)} where 1 ≤ i ≤ n
For instance, f(6,2) = 2^{w(1)} + 2^{w(2)} + 2^{w(3)} + 2^{w(4)} + 2^{w(5)} + 2^{w(6)} = 13
Given n and k, calculate f(n, k).
Input
The first line contains an integer t, denoting the number of test cases. Each of the next t lines contains two integers, n and k, separated by a single space. Sum of n will not exceed 10^{11} in an input file.Constraints
Output
For each case, output a line of the format Case X: Y, where X is the case number, starting from 1, and Y is the required answer. You can safely assume that the answer will fit in a signed 64 bit integer.Sample Input
10 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10
Sample Output
Case 1: 1 Case 2: 3 Case 3: 7 Case 4: 13 Case 5: 21 Case 6: 61 Case 7: 85 Case 8: 113 Case 9: 145 Case 10: 271
hide comments
Ishan:
20221027 13:16:26
I have found a way to do in to do till10^9 . :( . my recurrence relation has 3 params probably it can be done with 2 params. 

[Lakshman]:
20200621 15:42:58
@sgtlaugh Can you give some hint?


Francky:
20200611 11:17:56
Please update description :


nadstratosfer:
20200611 01:06:55
I don't know the solution to this one, but an easy version with n < 10^7, k < 140 and t > 10000 would be fun to solve efficiently as well  please consider setting it. Perhaps in Tutorial, but IMHO it'd make a popular classical problem too.

Added by:  sgtlaugh 
Date:  20200610 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own Problem 