Hermione Granger is very concerned about the magical disabilities of squibs (A Squib is someone who was born into a wizard family but hasnt 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+b2)modk=c3 modk, wherea≤b≤cand1≤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 (1 ≤ T ≤ 400) denoting the number of test cases. Then in each of the following T lines, there will be two integers n and k (1 ≤ n, k ≤ 105). 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 1 10 7 Sample Output Case 1: 27