당신은 이제 유명한 수학의 왕국 HSFZ에 있습니다. 따라서 몇 가지 수학 문제를 해결해야 합니다. 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$)가 주어지며, 이는 테스트 케이스의 개수를 나타냅니다. 각 테스트 케이스에 대해, 한 줄에 두 정수 $p, q$ ($1 \le p, q \le 10^4$)가 주어집니다.

출력

각 테스트 케이스에 대해, 네 정수 $a, b, c, d$ ($1 \le a, b, c, d \le 10^7$)를 한 줄에 출력하세요. 위 제약 조건 하에서 항상 해가 존재함을 증명할 수 있습니다.

예제

입력 1

2
1 1
9 28

출력 1

1 1 1 1
1 2 1 3