Description

最近60上数学课老是睡觉，于是老师就对他说，我给你出一道数学题，你如果可以做出来就可以在我课上睡觉，不然就得好好听课。
题目是这样的：给你一个n，你需要找到a,b,c,d四个正整数使得a+b+c+d=n并且gcd(a,b)=lcm(c,d)。（gcd是两个数的最大公约数，lcm是两个数的最小公倍数）
为了帮助60在课上肆无忌惮的睡觉（这是不好滴，小孩子不要学），你能告诉他正确答案是什么吗？

Format

Input

第一行是一个T（ 1 ≤ T ≤ 1e4 ）表示有T组案例
随后T行，每行有一个n（ 4 ≤ n ≤ 1e9 ）表示a,b,c,d的和

Output

输出T行，每行四个元素分别表示满足题意的a,b,c,d（a≥b≥c≥d），每两个数之间有一个空格，最后一个数后面没有空格，最后一行也要换行

Sample 1

Input

5
4
7
8
9
10

Output

1 1 1 1
2 2 2 1
2 2 2 2
4 2 2 1
5 3 1 1

Limitation

1s, 1024KiB for each test case.

Hint

Source

每日一题