You know you are now in HSFZ, the famous math kingdom. So you have to solve some math problems. You are given two positive integers $p, q$. Your task is to construct positive integers $a, b, c, d$ such that $1 \le a, b, c, d \le 10^7$ and $$ \frac{a^3+b^3}{c^3+d^3} = \frac{p}{q} $$

输入格式

Each test contains multiple test cases. The first line contains one integer $t$ ($1 \le t \le 10^6$), indicating the number of test cases. For each test cases, only one line contains two integers $p, q$ ($1 \le p, q \le 10^4$).

输出格式

For each test case, output one line contains four integers $a, b, c, d$ ($1 \le a, b, c, d \le 10^7$). It can be proved that a solution always exist under above constraints.

样例

输入 1

2
1 1
9 28

输出 1

1 1 1 1
1 2 1 3