Bạn Nhân rất thích làm việc với các con số và bạn ấy đang nghiên cứu một cách biểu diễn các số trong những hệ cơ số khác nhau. Với mỗi số nguyên dương ~n~ trong hệ thập phân có dạng ~n=\overline{{{a}_{k}}{{a}_{k-1}}...{{a}_{2}}{{a}_{1}}{{a}_{0}}},~ trong đó ~0\le {{a}_{i}}\le 9,i=\overline{0,k}~, Nhân viết nó thành

~n={{a}_{k}}{{10}^{k}}+{{a}_{k-1}}{{10}^{k-1}}+...+{{a}_{2}}{{10}^{2}}+{{a}_{1}}{{10}^{1}}+{{a}_{0}}{{10}^{0}}.~

Và Nhân đã nghĩ ra một hệ cơ số khá đặc biệt và bạn rất thích thú với nó, đặt tên là hệ ~10'~ phân. Một số viết trong hệ ~10'~ – phân dạng ~n={{\overline{{{a}_{k}}{{a}_{k-1}}...{{a}_{2}}{{a}_{1}}{{a}_{0}}}}_{(1{0}')}}~ với ~0\le {{a}_{i}}\le 9,i=0..k~ sẽ có giá trị trong hệ thập phân thông thường là

~n={{a}_{k}}({{10}^{k}}+1)+{{a}_{k-1}}({{10}^{k-1}}+1)+...+{{a}_{2}}({{10}^{2}}+1)+{{a}_{1}}({{10}^{1}}+1)+{{a}_{0}}({{10}^{0}}+1)~.

Bằng hệ cơ số này, Nhân có thể mã hóa một số nguyên dương ~K~ nào đó bằng cách nhân giá trị của nó trong hệ thập phân và trong hệ ~10'~ – phân lại để được một số nguyên dương ~N~. Nhân đang thắc mắc là với số nguyên dương ~N~ cho trước thì số nguyên dương ~K~ nhỏ nhất là bao nhiêu. Bạn hãy giúp Nhân thực hiện công việc này nhé, sắp tốt nghiệp tới nơi rồi, không còn thời gian để vét cạn nữa.

Yêu cầu. Cho số nguyên dương ~N~ thỏa mãn ~0<N<{{10}^{18}}~. Hãy tìm số nguyên dương ~K~ nhỏ nhất sao cho giá trị của nó trong hệ thập phân và trong hệ ~10'~ – phân có tích bằng ~N~.</p>

Input. Một dòng duy nhất là số nguyên dương ~N~.

Output. Một dòng duy nhất là số nguyên dương ~K.~ Nếu không có số ~K~ nào thỏa mãn thì in ra ~-1.~

Sample input 1.

2

Sample output 1.

1

Sample input 2.

110

Sample output 2.

10