Leeana Learned Few New Things Few Days Ago, Like:

1. Find The Summation Of Divisors.
2. Modular Arithmetic.

So Now Her Uncle Gave Her A Task.

Task Is: You Will Be Given A Number(N) And Another Number(K). Now You Have To Find  K_th Power Summation Of Divisors Of N.

Summation Of All Divisors Of N Will Be Huge,  So You Have To Print The Summation Module (M=1000000007).

Like: Divisors Of 6 is: ( 1 2 3 6 ) And K = 2.
so, summation is: 1^K+2^K+3^K+6^K = 1^2 + 2^2 + 3^2 + 6^2 = 1+4+9+36 = 50 % 1000000007 = 50

Leeana Thinks That You Are A Great Programmer, So She Needs Your Help. Can You Help Her??? :D :D :D 

Input

Input Starts With An Integer T (≤ 500), Denoting The Number Of Test Cases. Each Case Contains An Integer N (1 ≤ N ≤ 10¹⁵) And An Integer K (1 ≤ K ≤ 10⁵) Denoting The Power Of Divisors.

Output

For Each Test Cases, Print The Case Number And The Kth Power Summation  Of Divisors Of N Module 1000000007. After Each Case Print A New Line. See Sample Input And Output For Better Explanation.

Example

Input:
4
6 2
6 1
6 4
6 3

Output:
Case 1: 50
Case 2: 12
Case 3: 1394
Case 4: 252

#Extra_Challenge: N<=10^18, T<=1000 TL: 1s