In this challenge, you are given a triangular board of n rows. The first row has one block, and the following rows have a block more than the previous row. All the blocks have the same size and are numbered as in the first picture on the right. First, you must find the biggest rectangular area inside the triangular board, and then calculate the value of S which corresponds to the sum of the values belonging to the area found. If there are several areas with the same size, choose the area that maximizes the value of S. For example, in the second picture on the right, where n = 5, the maxi- mum rectangular area is (3 × 3), which is represented in the image. S = 4 + 5 + 6 + 8 + 9 + 10 + 13 + 14 + 15 = 84 Remember that the area of a rectangle is the multiplication of the two sides of the rectangle Input The first line of input contains an integer t (1 ≤ t ≤ 105) indicating the number of test cases that follow, one for line. Each test case contains a positive integer n (1 ≤ n ≤ 1011) indicating the number of rows. Output For each test case, you should print a line containing Case #x: y, where x is the test case number (starting from 1) and y is the sum obtained. Note that this value is very large, so print the result modulo 109 + 7. Sample Input 6 1 2 3 4 5 14 Sample Output Case #1: 1 Case #2: 5 Case #3: 16 Case #4: 42 Case #5: 84 Case #6: 3612