There are n teams participate in a contest.

There is exactly a match between each pair of teams (result in one team wins, other loses, no draw).

A triple team (A, B, C) is balanced iff A wins B, B wins C and C wins A.

Calculate the maximum of the number of balanced triple teams.

Input

The first line contains an integer T (T <= 10^5), denoting the number of test cases.

Each of T following line contains an integer n (n <= 10^6), denoting the number of teams in each test case.

Output

Each test case, print the maximum of the number of balanced triple teams in a single line.

Example

Input:
3
3
4
5 

Output:
1
2
5