There are n teams participating in a contest.

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

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

Calculate the maximum of the number of balanced triple teams.

Input

The first line contains an integer T (T ≤ 10⁵), denoting the number of test cases.

Each of T following line contains an integer n (n ≤ 10⁶), 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