Playing With Divisors

Your best friend is attending math class at the university. Teacher gave him two problems during the class.

• What is the sum of divisors of number $n$?

• What is the sum of the square of divisors of number $n$?

He was able to solve the first one. But that took him much time. He is also curious about the number of divisors of number $n$. But he has to solve it as soon as possible. He wants your help. He is your best friend so you do not want to turn him down. Now you know the number and its sum of divisors, you want to find number of divisors and sum of the square of divisors of that number.

You are given an integer number $n$ and its sum of divisors $s$. You have to tell the number of divisors and the sum of the square of divisors of number $n$.

Input

Input starts with an integer $T$ ($0 < T \le 500$), denoting the number of test cases. Each case contains an integer $n$ ($1 \le n \le 10^{16}$) denoting the number $n$ and an integer $s$ ($1 \le s \le 10^{18}$) denoting the sum of divisors $s$ of the number $n$.

Output

For each case, print the case number and number of divisors and sum of the square of divisors module $10^9+7$.

Sample

Input	Output
2 3 4 12 28	Case 1: 2 10 Case 2: 6 210