Федя был очень обрадован существованию такого понятия как НОД чисел.

Наибольшим общим делителем (НОД) двух натуральных чисел $$$m$$$ и $$$n$$$ называется наибольший из их общих делителей. Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух натуральных чисел, как наибольший из общих делителей всех этих чисел.

Но что такое НОД одного числа? Давайте считать что для натуральных чисел, это оно же. Однако Феде не нравится такое скучное обобщение и он придумал своё понятие — НПД.

Назовём наибольшим подстрочным делителем (НПД) числа наибольший общий делитель всех его непустых подстрок.

Подстрока — это непрерывная последовательность символов внутри строки. Например, у числа $$$171$$$ подстроки это числа: $$$1$$$, $$$17$$$, $$$171$$$, $$$7$$$, $$$71$$$ и $$$1$$$, а числа $$$11$$$ и $$$2$$$ не являются его подстроками.

По заданному числу $$$n$$$ найдите его НПД.