Một số được gọi là tự do nếu như trong biểu diễn thập phân của số đấy không có bất kỳ substring nào của nó là luỹ thừa của ~11~ trừ trường hợp số ~1~. Ví dụ số ~2404~ và ~13431~ là số tự do nhưng số ~911~ và số ~4121331~ không phải số tự do. ~F_n~ là số tự do thứ ~n~, cho số ~n~ yêu cầu bạn tính ~F_n~.

Input

Gồm nhiều dòng mỗi dòng là một số ~n (1 \leq n \leq 10^{18})~

Output

Gồm nhiều dòng mỗi dòng là là kết quả

Example

3
200
500000

3
213
531563