Незнайка решил открыть кружок по спортивному программированию. Для этого Незнайка сделал огромное количество визиток с qr-кодами и сложил их в одну стопку, забыв исходное напечатанное количество. Чтобы вспомнить, сколько было визиток, Незнайка выполнил $$$k$$$ последовательных действий. Он брал самую маленькую стопку визиток разбивал ее на две стопки по $$$a$$$ и $$$b$$$ визиток таким образом, чтобы в двух получившихся стопках было либо одинаковое количество визиток, либо чтобы количества визиток в стопках отличались ровно на 1 визитку, после чего возвращал эти стопки обратно к остальным. После всех $$$k$$$ действий Незнайка смог посчитать, что в самой маленькой стопке лежит ровно $$$n$$$ визиток.
Помогите Незнайке определить максимальное и минимальное количество визиток в исходной стопке.
Первая строка содержит целое число $$$t$$$ $$$(1 \le t \le 1600)$$$ – количество наборов входных данных.
Каждый набор входных данных содержит два целых числа $$$n$$$ и $$$k$$$ $$$(1\leq n,k\leq 40)$$$ — количество визиток в стопке после всех действий и количество действий, которое произвел Незнайка.
Для каждого набора входных данных выведите два целых числа, разделенных пробелом – максимальное и минимальное количество визиток, которое могло быть в изначальной стопке визиток.
В задаче 2 теста, ограничения для которых указаны ниже. Тесты из условия оцениваются в 0 баллов.
12 5
95 64
25 310 4
47 40 175 160
