Число, полностью состоящее из единиц называется репьюнитом. Определим R(k) как репьюнит длиной k; к примеру, R(6) = 111111.

Дано, что n – натуральное число, а НОД(n, 10) = 1. Можно показать, что всегда существует такое значение k, для которого R(k) делится нацело на n. Пусть A(n) будет наименьшим таким значением k; к примеру, A(7) = 6 и A(41) = 5.

Наименьшее значение n, при котором A(n) впервые превышает десять, равно 17.

Найдите наименьшее значение n, при котором A(n) впервые превысит один миллион.