Cəbrin fundamental teoremlərindən birində deyilir ki, \textbf{1}-dən böyük istənilən tam ədədi yeganə formada sadə ədədlərin hasili şəklində göstərmək olar. Lakin bu yeganə sadə vuruqlar dəstini müxtəlif üsullarla çeşidləmək olar. Məsələn: \textbf{k} ədədinin sadə vuruqlarını müxtəlif üsullarla çeşıdləmə sayını \textbf{f(k)} ilə işarə edək. Onda \textbf{f(10) = 2} və \textbf{f(20) = 3}. Sizə \textbf{n} müsbət tam ədədi verilir, istənilən \textbf{n} üçün həmişə elə \textbf{k} mövcuddur ki, \textbf{f}(\textbf{k}) =\textbf{ n} olsun. Belə minimal \textbf{k}-nı təyin edin. \InputFile Giriş faylı \textbf{1000}-dən çox olmayan test ehtiva edir və hər bir test ayrı sətirdə verilir. Hər bir test müsbət \textbf{n} (\textbf{n} < \textbf{2^63}) tam ədədini ehtiva edir. \OutputFile Hər bir test üçün elə \textbf{n} ədədini və ən kiçik \textbf{k} > \textbf{1} ədədini verin ki, \textbf{f(k) = n} olsun. Testlərdəki ədədlər elə seçilib ki, \textbf{k} < \textbf{2^63}.