Сегодня на очередном занятии в математическом кружке, посвященном теории чисел, Сережа узнал много новых для него интересных функций. В частности, ему очень понравилась функция $$$\varphi(n)$$$, которая определяется следующим образом: $$$\varphi(n)$$$ равно количеству натуральных чисел, не превосходящих $$$n$$$, взаимно-простых с $$$n$$$. Эта функция показалась Сереже очень красивой, так как на занятии он узнал несколько ее замечательных свойств. Например, для любых взаимно-простых чисел $$$a$$$ и $$$b$$$ верно, что $$$\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)$$$.

Напомним, что натуральные числа $$$a$$$ и $$$b$$$ называются взаимно-простыми, если их наибольший общий делитель равен единице. Например, числа $$$5$$$ и $$$8$$$ являются взаимно-простыми, а числа $$$12$$$ и $$$9$$$ — нет (их наибольший общий делитель равен $$$3$$$).

Приведем некоторые примеры значений функции $$$\varphi(n)$$$:

• $$$\varphi(5) = 4$$$ (натуральные числа, не превосходящие $$$5$$$, взаимно-простые с $$$5$$$: $$$1, 2, 3, 4$$$),
• $$$\varphi(1) = 1$$$ (существует всего одно натуральное число, не превосходящее $$$1$$$ — само число $$$1$$$),
• $$$\varphi(6) = 2$$$ (натуральные числа, не превосходящие $$$6$$$, взаимно-простые с $$$6$$$: $$$1, 5$$$).

Сережа очень любит натуральные числа из промежутка $$$[l, r]$$$, то есть числа $$$l, l + 1, \ldots, r$$$. Начинающему математику тут же захотелось исследовать поведение функции $$$\varphi(n)$$$ на промежутке $$$[l, r]$$$.

Сережа хочет найти такое натуральное число $$$x$$$, что $$$l \le x \le r$$$, а также $$$\varphi(x) \ge \varphi(y)$$$ для любого натурального числа $$$l \le y \le r$$$. Так как Сережа является начинающим математиком, он не справился с этой задачей, поэтому решить ее придется вам.