Алгоритм на языке C - игра с числами - число с 3 на месте

Я столкнулся с этим вопросом в интервью. Любое число с 3 в позиции имеет хотя бы одно кратное, содержащее все единицы. Например, кратное 3 равно 111, кратное 13 равно 111111. Учитывая число, заканчивающееся на 3, меня спросили, как лучше всего найти его кратное, содержащее все единицы. Теперь возможен прямой подход, когда вы не учитываете проблемы с пространством, но по мере роста числа, а иногда даже если это не так, int (или long int при этом !) в C не может содержать это кратное. Как оптимально реализовать такой алгоритм на C?