You are given an integer $r$.

Construct six pairwise distinct points $P_1,P_2,\ldots,P_6$ with integer coordinates such that all of the following conditions hold:

• $P_1$, $P_2$, $P_3$, and $P_4$ lie on one circle of radius exactly $r$;
• $P_3$, $P_4$, $P_5$, and $P_6$ lie on one circle;
• $P_1$, $P_2$, $P_5$, and $P_6$ lie on one circle;
• the three circles above are pairwise distinct.

The centers of all three circles do not have to have integer coordinates. The radii of the second and third circles do not have to be integer either. Only the coordinates of the six constructed points are required to be integer.

Input

The first line contains a single integer $t$ ($1\le t\le50$): the number of test cases.

Each of the next $t$ lines contains one integer $r$ ($1\le r\le150$): the required radius of the first circle.

Output

For each test case, print six lines. The $i$-th line must contain two integers $x_i$ and $y_i$ ($|x_i|,|y_i|\le10\,000$), denoting the coordinates of $P_i$.

If there are several valid constructions, print any one of them.

Examples

Input 1

1
10

Output 1

6 8
10 0
-8 -6
0 10
13 15
15 15

Note

The example shows one possible construction. Other valid constructions are accepted as well.