Project Euler #12: Highly divisible triangular number

_{This problem is a programming version of Problem 12 from projecteuler.net}

The sequence of triangle numbers is generated by adding the natural numbers. So the 'th triangle number would be . The first ten terms would be:

Let us list the factors of the first seven triangle numbers:

We can see that is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over divisors?

Input Format

First line , the number of testcases. Each testcase consists of in one line.

Constraints

Output Format

For each testcase, print the required answer in one line.

Sample Input

Sample Output

Explanation

Explained in statement.