# 2784. remainder

Let r be the remainder when (a-1)n + (a+1)n is divided by a2 .

For example, if a = 7 and n = 3, then r = 42: ( 63 + 83 = 728 )%49= 42. And as n varies, so too will r, but for a = 7 it turns out that rmax = 42.

The question is when given a , you must find rmax.

### 输入格式

The first line will be a number N(<=100), means that there’re N test cases , Then N lines follow,each with a number a(3<=a<=10000) as described above.

### 输出格式

Output one line,with the answer described above;

### 样例

Input
3
7
4
5

Output
42
8
20


70 人解决，98 人已尝试。

94 份提交通过，共有 223 份提交。

3.7 EMB 奖励。