Последнее время Поликарп стал часто пропускать сигналы своего будильника, всего лишь нужно было ввести комбинацию 4 8 15 16 23 42 и можно дальше сладко спать. К сожалению, он стал часто просыпать важные дела и решил покончить с этим.

На днях Поликарп купил себе новый будильник, представляющий из себя хитрое устройство, которое просто так не выключишь. Чтобы будильник перестал работать нужно ввести десятичное число, состоящее из цифр 0 и 1, которое будет делиться нацело на все свои циклические сдвиги. Циклический сдвиг числа — это число, полученное переносом первых нескольких цифр в конец. Например, для числа 4020 это будут числа 4020, 204, 2040 и 402.

Всё было бы так просто, если бы будильник не требовал каждый раз новую комбинацию. Поэтому Поликарп решил вводить каждое утро числа по порядку, начиная с числа 1. Но, он беспокоится, что у него когда-нибудь не получится ввести нужное число, поэтому Поликарп решил узнать K-ое по порядку число заранее. Помогите ему, он в долгу не останется.