#include<bits/stdc++.h>
using namespace std;

#define LL long long

LL ans[11234567], tans[11234567];

//book用来标记不可用作分母的数字，题目说小于1000，下面代码用到book的地方都是判断分母是否可用
bool book[11234];

//得到一个结果后，如果比ans更优，那么更新
bool better(int d) {
    for (int i = d; i >= 0; i--) {
        if (ans[i] != tans[i])
            return ans[i] == -1 || tans[i] < ans[i];
    }
}

//获得下一个比 a/b 小的 1/c
LL get_next(LL a, LL b) {
    for (LL i = 1; ; i++) {
        if (i <= 10000 && book[i])
            continue;
        if (b <= a * i)
            return i;
    }
}

bool dfs(int max_deep, LL from, LL aa, LL bb, int deep) {
    //如果到达最大深度，那么需要判断下，然后return
    if (deep == max_deep) {
        //判断最后的状态是否为 1/c 的形式，如果不算，那么当前状态不可表示原分数
        if (bb % aa)
            return false;
        if (bb <= 10000 && book[bb/aa])
            return false;
        tans[deep] = bb/aa;
        //如果当前解更优，那么更新ans
        if (better(deep))
            memcpy(ans, tans, sizeof(LL) * (deep+1));
        return true;
    }

    bool ok = false;

    //得到的 1/c 中 c 至少比上一次的分母大才可以 from 即是上一次的分母加一
    from = max(from, get_next(aa, bb));
    for (int i = from; ; i++) {
        if (i <= 10000 && book[i])
            continue;

        //如果剩下的递归次数，都是用 1/i 还小于 aa/bb 的话，那么当前 i 和比 i 大的数字不能用来做分母
        if (bb * (max_deep+1-deep) <= i * aa)
            break;
        tans[deep] = i;

        //计算 aa/bb - 1/i，gcd 用来约分
        LL b2 = bb*i;
        LL a2 = aa*i - bb;
        LL g = __gcd(a2, b2);
        if (dfs(max_deep, i+1, a2/g, b2/g, deep+1))
            ok = true;
    }
    return ok;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int cases = 1; cases <= n; cases++) {
        memset(book, 0, sizeof(book));
        LL a, b, k;
        scanf("%lld %lld %lld", &a, &b, &k);
        for (int i = 0; i < k; i++) {
            LL t;
            scanf("%d", &t);
            book[t] = true;
        }

        for (int i = 0; ; i++) {
            memset(ans, -1, sizeof(ans));
            if (dfs(i,get_next(a, b), a, b, 0))
                break;
        }

        printf("Case %d: %lld/%lld=", cases, a, b);
        for (int i = 0; ans[i] != -1; i++) {
            if (i)
                putchar('+');
            printf("1/%lld", ans[i]);
        }
        putchar('\n');
    }
}

#include<bits/stdc++.h>
using namespace std;

const int MAX = 30;

char rawData[6][MAX];
int data[MAX], n, ans, jump[MAX], cnt;

bool judge(int A[], int k) {
    for (int i = 0; i < 5; i++) {
        if ((A[i]>>k)&data[i])
            return false;
    }
    return true;
}

void codingData(int n) {
    ans = n*10, cnt = 0;
    memset(data, 0, sizeof(data));
    for (int i = 0; i < 5; i++) {
        scanf("%s", rawData[i]);
        for (int j = 0; j < n; j++) {
            if (rawData[i][j] == 'X') {
                data[i] |= (1<<j);
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        if (judge(data, i))
            jump[cnt++] = i;
    }
}

void attempt(int dep, int A[], int pos) {
    if (pos + (10 - dep) * jump[0] > ans)
        return;
    if (dep == 10) {
        ans = min(pos, ans);
        return;
    }
    for (int i = 0; i < cnt; i++) {
        if (judge(A, jump[i])) {
            int B[MAX] = {};
            for (int j = 0; j < 5; j++) {
                B[j] = (A[j]>>jump[i]) | data[j];
            }
            attempt(dep+1, B, pos + jump[i]);
        }
    }
}

int main() {
    while (~scanf("%d", &n) && n) {
        codingData(n);
        attempt(1, data, n);
        printf("%d\n", ans);
    }
}

int n;
__builtin_popcount(n);

#include<bits/stdc++.h>
using namespace std;

int g[16][16], gmask[16];
int visited[16];

int dfs(int u, int p, int open, int n) {
    visited[u] = 1;
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)
            continue;
        if (g[u][i] == 0 || i == p)
            continue;
        if (visited[i] || dfs(i, u, open, n))
            return 1;
    }
    return 0;
}

int checkChain(int open, int n) {
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)
            continue;
        int t = gmask[i]^(gmask[i]&open);
        int degree = __builtin_popcount(t);
        if (degree > 2)
            return 0;
    }

    int op = __builtin_popcount(open);
    int comp = 0;
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)
            continue;
        if (visited[i])
            continue;
        if (dfs(i, -1, open, n))
            return 0;
        comp++;
    }
    return op >= comp - 1;
}

int main() {
    int n, cases = 0;
    while (~scanf("%d", &n) && n) {
        memset(g, 0, sizeof(g));
        memset(gmask, 0, sizeof(gmask));
        while (true) {
            int a, b;
            scanf("%d %d", &a, &b);
            if (a == -1 && b == -1)
                break;
            a--, b--;
            g[a][b] = g[b][a] = 1;
            gmask[a] |= 1<<b, gmask[b] |= 1<<a;
        }

        int ret = 0x3f3f3f3f;
        for (int i = 0; i < (1<<n); i++) {
            int op = __builtin_popcount(i);
            if (op >= ret)
                continue;
            if (checkChain(i, n))
                ret = min(ret, op);
        }
        printf("Set %d: Minimum links to open is %d\n", ++cases, ret);
    }
}

import java.util.*;
import java.lang.*;

public class Determinant {

    public static void main(String[] Args){
        Scanner cin = new Scanner(System.in);
        int size = cin.nextInt();
        double[][] data = new double[size][size];

        //读取数据
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                data[i][j] = cin.nextDouble();
            }
        }

        //标记是否可以提前确定行列式为0
        boolean zero = false;
        //记录交换行后的正负号
        double sign = 1;

        //主体
        for (int row = 0; row < size-1; row++){

            //如果第i行第i个元素已经是0的话，就去找一行非零的行交换
            if (data[row][row] == 0) {
                boolean flag = false;
                for (int trow = row + 1; trow < size; trow++){
                    if (data[trow][row] != 0){
                        flag = true;
                        swap_row(row, trow, size, data);
                        sign *= -1;
                        break;
                    }
                }
                //如果一列全为0，那么行列式为0
                if (!flag)
                {
                    zero = true;
                    break;
                }
            }

            for (int trow = row + 1; trow < size; trow++){
                double k;
                //如果当前行已经为0，那么直接跳过，否则用row行乘-k加到trow行
                if (data[trow][row] == 0)
                    continue;
                k = data[trow][row] / data[row][row];
                for (int col = row; col < size; col++){
                    data[trow][col] += -k * data[row][col];
                }
            }
        }

        double ans;


        //整理答案并输出
        if (zero)
            ans = 0;
        else{
            ans = sign;
            for (int row = 0; row < size; row++){
                ans *= data[row][row];
            }
        }

        System.out.print(ans);
    }

    static void swap_row(int a, int b, int size, double data[][]){
        for (int i = a; i < size; i++){
            double temp = data[a][i];
            data[a][i] = data[b][i];
            data[b][i] = temp;
        }
    }
}

#include<bits/stdc++.h>
using namespace std;

int n, step, maxd;

string goal;

bool solve(int d, string now)
{
    if (d == maxd)
    {
        step = d;
        return now == goal;
    }

    int h = 0;
    for (int i = 0; i < n - 1; i++)
        if (now[i+1] - now[i] != 1)
            h++;

    if (h > 3 * (maxd - d))
        return false;

    for (int l = 0; l < n; l++)
    {
        for (int r = l; r < n; r++)
        {
            string slt = now.substr(l, r-l+1);
            string tail = now.substr(r+1);
            for (int k = 0; k < l; k++)
            {
                string il = now.substr(0, k);
                string ir = now.substr(k, l-k);
                if (solve(d+1, il+slt+ir+tail))
                    return true;
            }
        }
    }
    return false;
}

int main()
{
    int testCase = 0;
    while (~scanf("%d", &n) && n)
    {
        string data;
        for (int i = 0; i < n; i++)
        {
            int t;
            scanf("%d", &t);
            data += (char) t + '0';
        }

        goal = "";
        for (int i = '1'; i <= '0'+n; i++)
            goal += i;

        for (maxd = 0; maxd < n; maxd++)
            if (solve(0, data))
            {
                printf("Case %d: %d\n", ++testCase, maxd);
                break;
            }
    }
}

#include<bits/stdc++.h>
using namespace std;

const int MAX = 112;
const double EPS = 1e-8;

struct node
{
    double first;
    double second;
    double right;
    node (double first, double second, double right):first(first),second(second),right(right){}
};

int n;
double width, ans = -1;
vector<node> status;

node connect(node a, node b)
{
    double w = a.second + b.second;
    double la = b.second / w, lb = a.second / w;
    node ans = node(max(a.first + la, -lb + b.first), w,max(b.right + lb, -la + a.right));
    return ans;
}

void solve(vector<node> &status)
{
    if (status.size() == 1)
    {
        double t = status[0].first + status[0].right;
        if (t <= width + EPS)
            ans = max(ans, t);
        return;
    }

    for (int i = 0; i < status.size(); i++)
    {
        for (int j = 0; j < status.size(); j++)
        {
            if (i == j)
                continue;

            vector<node> nstatus;

            for (int k = 0; k < status.size(); k++)
            {
                if (k == i || k == j)
                    continue;
                nstatus.push_back(status[k]);
            }

            node a = status[i], b = status[j];
            node x = connect(a, b);

            if (x.first + x.right > width + EPS)
                continue;

            nstatus.push_back(x);
            solve(nstatus);
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        status.clear();
        ans = -1;
        scanf("%lf", &width);
        scanf("%d", &n);
        while (n--)
        {
            double w;
            scanf("%lf", &w);
            status.push_back(node(0.0, w, 0.0));
        }
        solve(status);
        if (ans < 0)
            puts("-1");
        else
            printf("%.16lf\n", ans);
    }
}

#include<bits/stdc++.h>
using namespace std;

const int MAX = 200+10;

struct Node
{
    int v[3], dist;
};

bool operator < (const struct Node& a, const struct Node& b)
{
    return a.dist > b.dist;
}

int vis[MAX][MAX], ans[MAX];

void update_ans(Node u)
{
    for (int i = 0; i < 3; i++)
    {
        int d = u.v[i];
        if (ans[d] < 0 || ans[d] > u.dist)
            ans[d] = u.dist;
    }
}

void solve(int a, int b, int c, int d)
{
    int cap[3] = {a,b,c};
    memset(vis, 0, sizeof(vis));
    memset(ans, -1, sizeof(ans));
    Node start;
    start.v[0] = 0, start.v[1] = 0, start.v[2] = c;
    start.dist = 0;
    priority_queue<Node> q;
    q.push(start);
    vis[0][0] = 1;

    while (!q.empty())
    {
        Node u = q.top(); q.pop();
        update_ans(u);

        if (ans[d] >= 0)
            break;

        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (i == j)
                    continue;
                if (u.v[i] == 0 || u.v[j] == cap[j])
                    continue;

                int amount = min(cap[j], u.v[i] + u.v[j]) - u.v[j];
                Node u2;
                memcpy(&u2, &u, sizeof(u));
                u2.dist = u.dist + amount;
                u2.v[i] -= amount;
                u2.v[j] += amount;
                if (!vis[u2.v[1]][u2.v[0]])
                {
                    vis[u2.v[1]][u2.v[0]] = 1;
                    q.push(u2);
                }
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        solve(a, b, c, d);
        while (d >= 0)
        {
            if (ans[d] >= 0)
            {
                printf("%d %d\n", ans[d], d);
                break;
            }
            d--;
        }
    }
}

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int v;
    long long w;
    node(int v, long long w):v(v),w(w){}
};

vector<node> edges[112];
bool book[112];
long long dis[112][11];
int s, e, x;
int n, m;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d", &n, &m);
        memset(book, 0, sizeof(book));
        memset(dis, -1, sizeof(dis));
        for (int i = 0; i < n; i++)
            edges[i].clear();

        for (int i = 0; i < m; i++)
        {
            int u, v;
            long long w;
            scanf("%d %d %lld", &u, &v, &w);
            edges[u].push_back(node(v,w));
        }

        scanf("%d %d %d", &s, &e, &x);
        queue<int> q;
        q.push(s);
        dis[s][0] = 0;

        while (!q.empty())
        {
            int u = q.front();

            for (int i = 0; i < edges[u].size(); i++)
            {
                int v = edges[u][i].v;
                long long w = edges[u][i].w;
                for (int k = 0; k < x; k++)
                {
                    if (dis[u][k] != -1 && (dis[v][(k+1)%x] > dis[u][k] + w || dis[v][(k+1)%x] == -1))
                    {
                        dis[v][(k+1)%x] = dis[u][k] + w;
                        if (!book[v])
                        {
                            q.push(v);
                            book[v] = 1;
                        }
                    }
                }
            }
            book[u] = 0;
            q.pop();
        }

        if (dis[e][0] == -1)
            printf("No Answer!\n");
        else
            printf("%lld\n", dis[e][0]);
    }
}