今、あなたは数学の有名な王国、HSFZにいます。そのため、いくつかの数学の問題を解かなければなりません。 2つの正整数 $p$ と $q$ が与えられます。あなたの仕事は、$1 \le a, b, c, d \le 10^7$ を満たす正整数 $a, b, c, d$ を構成し、 $$ \frac{a^3 + b^3}{c^3 + d^3} = \frac{p}{q} $$ とすることです。

入力

入力には複数のテストケースが含まれる。最初の行には整数 $t$ ($1 \le t \le 10^6$) が含まれ、テストケースの数を示す。 各テストケースについて、1行に2つの整数 $p, q$ ($1 \le p, q \le 10^4$) が与えられる。

出力

各テストケースについて、4つの整数 $a, b, c, d$ ($1 \le a, b, c, d \le 10^7$) を1行に出力せよ。 与えられた制約の下で、常に解が存在することが示せる。

入出力例

入力例 1

2
1 1
9 28

出力例 1

1 1 1 1
1 2 1 3