BUET Inter-University Programming Contest

Problem F – Finding Magic Triplets

Problem

Hermione Granger is very concerned about the magical disabilities of squibs (A Squib is someone who was born into a wizard family but hasn’t got any magic powers). Since the fall of Voldemort, she has been working hard to invent a potion to cure these disabilities. After a lot of research work, she has invented that a certain amount of apple juice needs to be mixed with the burnt leaves of birch tree in a lot of cherry juice. Later, she invents that for a k-year old person, if a amount of apple juice, b amount of leaves of birch tree and c amount of cherry juice are mixed, it must satisfy the following equation:

(a + b²) mod k = c³ mod k, where a<=b<=c and 1<= a, b, c <= n.

She names such a triplet (a, b, c) as a magic triplet for a k-year old person. She wants to know how many different magic triplets exist for known values of n and k. A triplet is different from another if any of the three values is not same in both triplets.

Input

First line of the input contains a single positive integer T denoting the number of test cases. Then in each of the following T lines, there will be two integers n and k .

Output

For each of the cases, output a single line containing “Case x: y”, where x is the case number and y is the number of magic triplets.

Sample Input		Output for Sample Input
1 10 7		Case 1: 27
Problemsetter:	Anindya Das
Special Thanks:	Kazi Rakibul Hossain and Tasnim Imran Sunny