妹妹們

你知道御坂美琴總共有$20002$位妹妹嗎？通常把她們簡稱為御坂妹妹Sisters，由於平時這些妹妹沒有什麼事情可以做，一位實驗室的研究員拿了一個古老的玩具「河內塔」給大家打發時間。由於妹妹們的記憶能力彼此相通，因此他們可以構成一個驚人的神經網路計算任何事物，一般的河內塔輕而易舉的就被妹妹們破解了，得到答案的研究員覺得記憶相通的能力十分有趣，要提高問題的難度來考驗她們的能力：找出$4$根杆子的河內塔的最佳策略，如何使用最少的移動步數把所有盤子從$1$號柱子移動到$4$號柱子。

經過了些許時間，御坂妹妹給出了下列的演算法，假設$m$杆$n$盤的最少步為函數$f(m,n)$：

由$1$到$N$枚舉$t$，尋找最好的$t$。
先將前$t$盤利用$m$杆移到第$2$杆，花$f(m,t)$步。
再將後$n−t$盤利用$m−1$杆移到最末杆，花$f(m−1,n−t)$步。
最後把前$t$盤利用$m−1$杆從第2杆移到最末杆，花$f(m,t)$步。

根據御坂妹妹的演算能力，可以保證上演算法可以找出$4$根杆子的河內塔最少的移動步數，不過此時妹妹們已經消耗了極為大量的腦力，暫時無法活動。因此獲得了這一個演算法的你，可以親自操作河內塔來驗證方法的正確性嗎？

輸入說明

本題為互動題，提供以下三個函數可供使用，如果操作不合法的操作可能會得到$WA$或是$RE$：

int init();

回傳一個數字，表示盤子的數量$N$，請在程式一開始執行時呼叫此函數，本函數只能使用一次。

void move(int k,int from,int to);

把編號k的盤子從桿子from移動到桿子to

void finish();

表示執行完所有移動，結束程式。

保證：$0\leq N < 64$。

輸出說明

本題目沒有輸出。輸出任何文字會得到$WA$。

範例測試

N = 4
最佳解只要9個步驟

這是一個會通過範例測試的程式

int main(){
    int n = init();
    move(1,1,2);
    move(2,1,4);
    move(3,1,3);
    move(2,4,3);
    move(4,1,4);
    move(2,3,1);
    move(3,3,4);
    move(2,1,4);
    move(1,2,4);
    finish();
    return 0;
}

Judge Setting

run-time limit: 100 ms
memory limit: 131072 byte
測資數量: 0