Теперь вы находитесь в HSFZ, знаменитом королевстве математики. Поэтому вам предстоит решить несколько математических задач. Вам даны два целых положительных числа $p$ и $q$. Ваша задача — построить целые положительные числа $a, b, c, d$ такие, что $1 \le a, b, c, d \le 10^7$ и $$ \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