Farmer John 拥有一个农场。他首先建造了一个圆形围栏。然后，他会选择 $n$ 个点，并建造一些连接这些点的直线围栏。接下来，他要在每个区域内喂养一头奶牛，这样奶牛们就不会在不破坏围栏的情况下互相嬉戏。为了喂养更多的奶牛，他还希望拥有尽可能多的区域。然而，他现在正忙于建造围栏，所以他需要你的帮助来确定如果他适当地选择这 $n$ 个点，他最多能喂养多少头奶牛。

输入格式

第一行包含一个整数 $1 \le T \le 100000$，表示测试用例的数量。对于每个测试用例，有一行包含一个整数 $n$。保证 $1 \le T \le 10^5$ 且 $1 \le n \le 10^{18}$。

输出格式

对于每个测试用例，你应该输出一行 "Case #i: ans"，其中 $i$ 是测试用例编号（从 1 开始），$ans$ 是农场主 John 最多能喂养的奶牛数量除以 $10^9 + 7$ 的余数。

样例

输入格式 1

3
1
3
5

输出格式 1

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