Description

求有多少个三元组(a, b, c)满足1<=a<=b<=c<=n且 a+b^2≡c^3 (mod k)

Format

Input

第一行一个整数T，表示数据组数。

以下T行，每行两个整数n, k。

1 <= n, k <=10^5, 1 <= T <= 400

Output

对每组数据输出单独一行"Case t: x"，t是数据组数，x是答案。

Samples

1
10 7

Case 1: 27