F. История о юноше, изучавшем математику, когда попал в другой мир
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Когда у Акито прошла голова, он решил изучить математику, а способы изучения математики в другом мире немного отличаются от наших.

В очередной задаче у Акито есть колода из $$$n$$$ двусторонних карт, на лицевой стороне $$$i$$$-й карты написана цифра $$$x_i$$$, а на оборотной стороне цифра $$$y_i$$$. Акито должен выложить эти карты на столе слева направо в произвольном порядке. Каждую карту можно класть лицевой стороной вверх или вниз.

После этого придёт Учитель, прочитает последовательность цифр на картах как целое десятичное число $$$m_1$$$, а потом перевернёт все карты и прочитает новую последовательность как целое десятичное число $$$m_2$$$. Разумеется, в $$$m_1$$$ и $$$m_2$$$ не должно быть ведущих нулей.

Оценкой Акито за это задание будет целое число $$$d = |m_1 - m_2|$$$, но важно заметить, что в другом мире чем меньше оценка, тем лучше.

Помогите Акито получить минимальную оценку.

Входные данные

В первой строке дано число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов данных.

В первой строке каждого набора данных дано число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество карт в колоде.

В следующих $$$n$$$ строках даны числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \le x_i, y_i \le 9$$$) — цифры на $$$i$$$-й карте колоды.

Гарантируется, что сумма $$$n$$$ по всем наборам данных не превышает $$$2 \cdot 10^5$$$. Для каждого набора данных гарантируется, что есть хотя бы одна карта, на которой обе цифры ненулевые.

Выходные данные

Для каждой колоды карт требуется вывести два числа — полученные $$$m_1$$$ и $$$m_2$$$, минимизирующие $$$|m_1 - m_2|$$$

Пример
Входные данные
6
3
1 1
3 3
2 2
4
0 2
1 0
9 9
0 6
1
6 9
5
1 2
3 4
5 6
7 8
9 0
4
5 2
2 5
5 2
2 5
2
1 0
5 2
Выходные данные
312
312
9062
9100
6
9
40571
39682
5222
2555
50
21
Примечание

В первом наборе данных любая перестановка карт даст $$$d = 0$$$, так как все цифры на сторонах карт одинаковые.

В четвёртом наборе данных также подойдут $$$m_1 = 59842$$$ и $$$m_2 = 60731$$$, так как $$$d = |m_1 - m_2| = 889$$$ в обоих случаях. Можно показать, что $$$d \lt 889$$$ получить нельзя.

В последнем наборе данных оптимально было бы взять $$$m_1 = 12, m_2 = 05 = 5$$$, но ведущих нулей в числах не должно быть, поэтому число $$$m_2 = 05$$$ не подходит. Из-за этого оптимальным $$$d$$$ является $$$d = |50 - 21| = 29$$$