Перо, пред да заспие, решил да вежба математика. Тој избрал позитивен цел број K (K > 1). Потоа започнал од 0 и цело време додавал K на добиениот број. По некое време престанал со додавање, па продолжил добиениот број да го множи со K. Продолжил со множење сè додека не заспал.

Следното утро, Перо не бил сигурен дали бројот X, до кој памети дека стигнал, може да биде добиен со овие операции. Тој сака да провери дали е можно да се добие X и ако е можно, да го одреди минималниот број на операции (нула или повеќе операции собирање плус нула или повеќе операции множење) потребни за да стигне до X.

Влез

Во првиот и единствен ред дадени се два цели броеви: K (1 < K < 10¹⁵) и X (0 ≤ X ≤ 10¹⁵).

Забелешка. За 20% поени од тест случаите бројот ќе може да се добие само со операцијата собирање (минимален број на операции).
За други 10% поени од тест случаите бројот ќе може да се добие само со операцијата множење после само една операција собирање (минимален број на операции).
За првите 60% поени од тест случаите ќе важи: K (1 < K < 100) и X (0 ≤ X ≤ 1 000 000).

Излез

Во еден ред отпечатете го минималниот број на операции со кои Перо би можел да го добие бројот X. Доколку не постои никаков начин Перо да го добие бројот X според постапката претставена во задачата, отпечатете -1.

Ограничувања

Временско ограничување: 100 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
2 6

излез
3

влез
2 8

излез
3

влез
4 48

излез
4

влез
3 28

излез
-1