If you are given two sides of a rectangle, you can find the area of the rectangle very easily. But can you do the opposite? Given the area of a rectangle can you tell me how many different rectangles can have this area, provided the sides of the rectangles must be integer? Two rectangles are equal only if the sides are same. You cannot rotate a rectangle. So if the area is 6 there are 4 different rectangles are possible. They are 1x6, 2x3, 3x2 and 6x1. This problem is very easy and I am sure you can solve it in a minute. Your problem is much tougher. One of your friends Po has got a magic Genie. Every day the Genie grants Po a wish. When asked to grant the wish, the Genie (depending on its mood) tells a number. If it’s positive then Po’s land gets multiplied by that number. If it’s negative then Po’s land is divided by the absolute value of that number. So every day, Po tells you the area of the land Po owns. You need to find out how many different rectangles can have that area. And then output the summation after D days. Initially the area of land Po owns is 1. Input First line of input consists of an integer, T (T ≤ 10), the number of test cases. Each case starts with an integer, D (0 < D ≤ 106), the number of days this wish granting will go on. Next D lines each has an integer G (0 < |G| ≤ 106), the number with which Po’s lands area will be multiplied or divided. If G is negative, it will be a divisor of Po’s land area. Output For each case print one line ‘Case X:’ where X is the case number. Then for each wish of a day, find the number of different of rectangles you can make which will have the same area as Po’s land and output the summation after D days. As this can be much bigger, output modulo 1000000007 (109 + 7). Sample Explanation: 1st day: Area = 12 → 6 ways. 2nd day: Area = 36 → 9 ways. 3 day: Area= 18 → 6 ways. 4 day: Area = 90 → 12 ways. 5day: Area=15→4ways. So in total (6+9+6+12+4) = 37 ways. Sample Input 1 5 12 3 -2 5 -6 Sample Output Case 1: 37