Problem Description

Farmer John owns a farm. He first builds a circle fence. Then, he will choose $n$ points and build some straight fences connecting them. Next, he will feed a cow in each region so that cows cannot play with each other without breaking the fences. In order to feed more cows, he also wants to have as many regions as possible. However, he is busy building fences now, so he needs your help to determine what is the maximum number of cows he can feed if he chooses these $n$ points properly.

:::align{center} :::

Input Format

The first line contains an integer $1 \le T \le 100000$, the number of test cases. For each test case, there is one line that contains an integer $n$. It is guaranteed that $1 \le T \le 10^5$ and $1 \le n \le 10^{18}$.

Output Format

For each test case, you should output a line "Case #$i$: ans" where $i$ is the test case's number, starting from $1$ and ans is the remainder of the maximum number of cows farmer John can feed when divided by $10^9 + 7$.

3
1
3
5

Case #1: 1
Case #2: 4
Case #3: 16