Giải bài trực tuyến

Songuku95 đố hgminh95 một bài toán như sau:

Xếp n củ Carrot trên một hình tròn ( các củ carrot được đánh số từ 1 -> n)

Khánh lấy n đoạn dây buộc 2 củ carrot liên tiếp lại (Cử 1 buộc với củ 2, củ 2 buộc với củ 3, …, củ n-1 buộc với cử n, củ n buộc với củ 1)

Bây giờ Songuku95 đố HgMinh95 bỏ một vài đoạn dây nối đi sao cho mỗi củ carrot còn ít nhất 1 đoạn dây nối. HgMinh95 thông minh vốn sẵn tính trời nên việc này hoàn toàn là đơn giản với HgMinh95 (Thực chất chả bỏ dây nào cũng đã đúng rồi :3)

Cơ mà sau đấy, Songuku95 lại thách HgMinh95 đếm số cách bỏ một vài đoạn dây để vẫn thỏa mãn “mỗi củ carrot còn ít nhất 1 đoạn dây nối”. Bài toán này làm hgminh trằn trọc suy nghĩ suốt nhiều ngày liền. Vì quá khó nên HgMinh95 đã nhờ đến sự cứu trợ từ người không quen (hoặc quen) :))

Các bạn hãy giúp HgMinh95 bài toán này nhé.

Input

Cho số test là T (t <= 5)

T dòng tiếp theo chứa  T số nguyên N (3 <= N <= 50000)

Output

Gồm T dòng

Dòng thứ i in ra số R = số cách bỏ một vài đoạn dây sao cho mỗi củ carrot vẫn còn ít nhất 1 dây nói đến nó.

Example

Input:

2
3
6

Output:

4
18

Giải thích 

N=3. Có 4 cách xóa:
Không xóa cạnh nào, xóa cạnh 1-2, xóa cạnh 2-3, xóa cạnh 3-1 

Giới hạn
20% số test có N <= 25