Given an integer n, your task is to compute the following sums:

• The sum S of the n first integers (starting from 1)
• The sum S_even of the n first even integers (starting from 2)
• The sum S_odd of the n first odd integers (starting from 1)
• The sum S_squares of the n first squares of integers (1, 4, 9, ...)
• The sum S_cubes of the n first cubes of integers (1, 8, 27, ...)

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case is described in a single line containing the integer « n » (1 ≤ n ≤ 10⁴ ).

Output

For each test case, print a single line containing five space-separated integers: S S_even S_odd S_squares S_cubes

Example

Input:
3
4
5
6

Output:
10 20 16 30 100
15 30 25 55 225
21 42 36 91 441