Do you know the childhood story of Carl Friedrich Gauss? He was of course the most talented kid in the class. Math teacher could hardly finish giving mathematics problem; Gauss was ready with his answer. One day being annoyed, the teacher asked Gauss to add numbers from 1 to 100. The teacher was thinking that now he will be relieved from Gauss, cause adding 100 numbers is not an easy task. But guess what! Gauss was ready with his answer again. Anyway, I would not describe how he added all those numbers in such a short time but want to share a news. I think Gauss has reborn! In my class there is a kid who is extremely talented. Like Gauss I hardly finish giving him problem. In 5 years age he can sum fractions! Can you imagine? You remember how to add fractions right? If you have two fractions say a/b and c/d then their sum is (ad+bc)/bd. Sometimes we divide numerator and denominator with a number to bring it to reduced form. Tomorrow I am going to give him a problem which is supposed to take a long time to solve. The problem is: Given two numbers n and k. For 1 ≤ a,c,d,k ≤ n and b = k, how many tuples (a,b,c,d) are there such that a/b and c/d sum up to (ad + bc)/bd and this sum is in reduced form. A fraction is in reduced form if the numerator and denominator have no common divisor other than 1. Well, I don’t want to taketherisk,Iwillaskforsumofalla,sumofallb,sumofallcandsumofalldalso. Ihopehewont disturb me anymore within this week. But in case he turns in earlier I want you to help me to verify his answer. Input First line of the test file contains a positive integer T (T ≤ 100). Hence follows T cases, each case starts with two positive integers n and m. (n ≤ 100000 and m ≤ 100). Hence follows m space separated positive integers in the following line. These are the values of k (k ≤ n). Output For each case, output the case number, followed by m lines. Each line contains five numbers the number of tuples, sum of a, sum of b, sum of c and sum of d. Since the answers may be big print them modulo 71211919. If you are wondering why the mod is such peculiar, then I must say it is numerical form of Gauss. Sample Input 2 22 12 33 123 Sample Output Case 1: 69688 22432 Case 2: 21 42 21 39 39
2/2 10 20 20 18 18 10 15 30 20 14