\(\text{\)gcdSum\(}\) положительного целого числа — это \(gcd\) этого числа и суммы его цифр. Формально, \(\text{\)gcdSum\(}(x) = gcd(x, \text{ сумма цифр } x)\) для положительного целого \(x\). \(gcd(a, b)\) обозначает наибольший общий делитель \(a\) и \(b\) — наибольшее целое число \(d\), такое, что оба числа \(a\) и \(b\) делятся на \(d\).
Например: \(\text{\)gcdSum\(}(762) = gcd(762, 7 + 6 + 2)=gcd(762,15) = 3\).
Вам дано целое число \(n\). Найдите наименьшее целое число \(x \ge n\), для которого \(\text{\)gcdSum\(}(x) > 1\).
Примечание
Объяснение трех наборов входных данных из примера:
Набор 1: \(n = 11\):
\(\text{\)gcdSum\(}(11) = gcd(11, 1 + 1) = gcd(11,\ 2) = 1\).
\(\text{\)gcdSum\(}(12) = gcd(12, 1 + 2) = gcd(12,\ 3) = 3\).
Значит, минимальное целое число \(\ge 11\), для которого \(gcdSum\) \(> 1\) — это \(12\).
Набор 2: \(n = 31\):
\(\text{\)gcdSum\(}(31) = gcd(31, 3 + 1) = gcd(31,\ 4) = 1\).
\(\text{\)gcdSum\(}(32) = gcd(32, 3 + 2) = gcd(32,\ 5) = 1\).
\(\text{\)gcdSum\(}(33) = gcd(33, 3 + 3) = gcd(33,\ 6) = 3\).
Значит, минимальное целое число \(\ge 31\), для которого \(gcdSum\) \(> 1\) — это \(33\).
Набор 3: \(\ n = 75\):
\(\text{\)gcdSum\(}(75) = gcd(75, 7 + 5) = gcd(75,\ 12) = 3\).
\(\text{\)gcdSum\(}\) числа \(75\) уже \(> 1\). Значит, это число и является ответом.