Bạn đang ở HSFZ, vương quốc toán học nổi tiếng. Vì vậy, bạn phải giải một số bài toán. Cho hai số nguyên dương $p$ và $q$. Nhiệm vụ của bạn là xây dựng các số nguyên dương $a, b, c, d$ sao cho $1 \le a, b, c, d \le 10^7$ và $$ \frac{a^3 + b^3}{c^3 + d^3} = \frac{p}{q} $$

Dữ liệu vào

Mỗi bài kiểm tra gồm nhiều trường hợp kiểm tra. Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^6$), cho biết số lượng trường hợp kiểm tra. Với mỗi trường hợp kiểm tra, một dòng duy nhất chứa hai số nguyên $p, q$ ($1 \le p, q \le 10^4$).

Dữ liệu ra

Với mỗi trường hợp kiểm tra, in ra một dòng chứa bốn số nguyên $a, b, c, d$ ($1 \le a, b, c, d \le 10^7$). Có thể chứng minh rằng luôn tồn tại một lời giải dưới các ràng buộc đã cho.

Ví dụ

Đầu vào 1

2
1 1
9 28

Đầu ra 1

1 1 1 1
1 2 1 3