Натуральное число называется двояким, если в его десятичной записи встречается не более двух различных цифр. Например, числа 3, 23, 33, 100, 12121 — двоякие, а числа 123 и 9980 — нет.

Дан набор натуральных чисел. Для каждого из них найдите ближайшее к нему двоякое число. Если ближайших несколько, следует выводить меньшее из них.

В первой строке входных данных находится число N — количество чисел, для которых нужно найти двоякие. В следующих строках по одному в строке находятся положительные целые числа. Размер входных данных не превышает 1 МиБ (1 МиБ = 2²⁰ байт).

Выведите по одному двоякому числу для каждого из N чисел во вводе в том порядке, в каком они идут во входных данных.

Примеры

Входные данные	Выходные данные
3 123 2012 11111	122 2020 11111