Істина, схована у рекурентності

Вхідні дані

Кожен рядок містить три цілі числа: $k$ (0 < k < 10^{19}), $n$ (0 < n < 10^{19}) і $t$ (0 < t < 10). Останній рядок містить три нулі і не повинен оброблятися.

Вихідні дані

Для кожного тесту виведіть номер тесту та значення $x$ в окремому рядку. Формат виводу показано у зразку.

Приклади