//920 - Sunny Mountains (by Snail)
#include <iostream>
#include <algorithm>    // for sort()
#include <cmath>        // for sqrt()
#include <iomanip>      // for setprecision()
using namespace std;

struct point {double x, y;} l[100];             // l(andscape)[] -- 地形
inline bool xlt (point a, point b) {return a.x < b.x;}
            // xlt (x less than)--x 小於(按 x 由小到大排序)
int main () {
    int n, i, tc;
    double len, y, dy, dx;
    cout << fixed << setprecision(2);           // 小數以下兩位
    cin >> tc;
    while (tc--) {
        cin >> n;
        for (i=0; i<n; i++)
            cin >> l[i].x >> l[i].y;
        sort (l, l+n, xlt);
        len = y = 0;                            // y-- 目前高度
        for (i=n-2; i>=0; i--) {
            if (l[i].y > y) {
                dy = l[i].y - y;                // d(elta)y -- 高度差
                dx = (l[i].x - l[i+1].x) * dy / (l[i].y - l[i+1].y);
                len += sqrt (dx*dx + dy*dy);
                y = l[i].y;
            }
        }
        cout << len << endl;
    }
}

//729 - The Hamming Distance Problem (by Snail) 0.228s
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main () {
    int tc, n, h;
    string s;
    cin >> tc;
    while (tc--) {
        cin >> n >> h;
        s.assign (n-h, '0');                    // 設定為 n -h 個 '0'
        s.append (h, '1');                      // 加上 h 個 '1'
        do {
            cout << s << endl;                  // 輸出所有的排列
        } while (next_permutation (s.begin(), s.end()));
        if (tc) cout << endl;                   // 測資間空一行
    }
}

//756 - Biorhythms (by Snail) 0.024s
#include <iostream>
using namespace std;

int main () {                       // 5544 = 28*33* 6 = 23*241 + 1
    int tc=1, p, e, i, d;           // 14421 = 23*33*19 = 28*515 + 1
    while (cin >> p, p>=0) {        // 1288 = 23*28* 2 = 33* 39 + 1
        cin >> e >> i >> d;
        d = (p*5544 + e*14421 + i*1288 - d + 21251) % 21252 + 1;
        cout << "Case " << tc++ << ": the next triple peak occurs in" << d << "days.\n";
    }
}   // 中國餘數定理(韓信點兵)

//11463 - Commandos (by Snail)
#include <iostream>
using namespace std;

int main () {
    int m[101][101], i, j, k, N, R, u, v, s, d, t, tc, ntc;
    cin >> ntc;
    for (tc=1; tc<=ntc; tc++) {
        cin >> N >> R;
        for (i=0; i<N; i++) {                   // 初始化
            for (j=0; j<N; j++)
                m[i][j] = 101;                  // 101-- 無法到達
            m[i][i] = 0;
        }
        for (i=0; i<R; i++) {
            cin >> u >> v;
            m[u][v] = m[v][u] = 1;
        }
        for (k=0; k<N; k++)                     // Floyd-Warshall
            for (i=0; i<N; i++)
                for (j=0; j<N; j++)
                    m[i][j] = min(m[i][j], m[i][k]+m[k][j]);
        cin >> s >> d;
        t = 0;
        for (k=0; k<N; k++)
            t = max(t, m[s][k]+m[k][d]);        // s→k→d 的最大值
        cout << "Case " << tc << ": " << t << endl;
    }
}

//929 - Number Maze (by Snail) 2.068s
#include <iostream>
#include <queue>
using namespace std;

int cost[1000][1000];           // 原本儲存該格所讀入的數字
                                // 拜訪過後則以負數表示從原點到該格的距離
struct cell {
    int r, c;
    cell (int r, int c) : r(r), c(c) {}         // constructor -- 建構器
} p(0, 0);

struct gt {                                     // 給優先佇列用的 Functor
    bool operator() (cell a, cell b) {
        return cost[a.r][a.c] < cost[b.r][b.c]; // 依該格的 Cost 來排序
    }
};

int main () {
    int tc, n, m, i, j, d;
    int dr[4]={0, 0, 1, -1}, dc[4]={1, -1, 0, 0};     // d(elta) -- 四個方向的座標差
    cin >> tc;
    while (tc--) {
        cin >> n >> m;
        for (i=1; i<=n; i++)                    // 輸入 cost
            for (j=1; j<=m; j++)
                cin >> cost[i][j];
        priority_queue<cell, vector<cell>, gt> q;// 建構新的優先佇列
        q.push (cell(1, 1));                    // 將原點推入佇列
        cost[1][1] = ~cost[1][1];               // 標示為拜訪過
        while (p=q.top(), p.r!=n || p.c!=m) {   // BFS + Priority Queue
            q.pop();                            // 從佇列取出
            for (d=0; d<4; d++) {               // 試四個方向
                i = p.r + dr[d];
                j = p.c + dc[d];
                if (i<1 || i>n || j<1 || j>m || cost[i][j]<0)
                    continue;                   // 超出邊界或拜訪過則跳過
                cost[i][j] = cost[p.r][p.c] - cost[i][j];
                q.push (cell (i, j));           // ↑計算從原點到此的距離
            }
        }
        cout << ~cost[n][m] << endl;
    }       // 用 - 無法把 0 變負數，所以用~
}