We have n cities that are connected by m bi-direction roads. Each city has a unique id from 1 to n, so we have cities c₁,..., c_n. Let r_ij be the road connecting two cities c_i and c_j, then r_ij has a length l_ij and condition d_ij, where the length is a positive integer and the condition is an integer from 1 to k. Note that all roads are bidirectional so l_ij is equal to l_ji and d_ij is the same as d_ji.

We want to drive a car from a starting city c_s to a destination city c_d along a shortest route. However, the condition of a road has a severe impact on the suspension system of our car. That is, after driving through a road of condition c, we cannot drive through another road of condition c immediately, otherwise the suspension of our car will break down. For example, if road r₁₂ has condition 1 and r₂₃ also has condition 1, then we cannot drive from c₁ to c₂ to c₃. However, if road r₁₂ has condition 1, r₂₃ has condition 2, and r₃₄ also has condition 1, then we can drive from c₁ to c₂ to c₃ to c₄, since we did not drive through two roads of the same condition consecutively.

Now given the condition and length of all roads and p pairs of starting and destination city pairs, please compute the shortest path for each pair of cities without going through two consecutive roads of the same condition.

Technical Specifications

1. The number of cities n is no more than 50.
2. The number of roads m is no more than 500.
3. The number of conditions k is no more than 50.
4. The number of source and destination city pairs p is no more than 15.
5. The length of each l_ij is at most 2¹⁵.

Input 

The first line of the input file contains an integer, denoting the number of test cases to follow. The first line of each test case has the number of cities n, the number of roads m, the number of conditions k, and the number of city pairs p to compute the distance. Each of the next m lines has the information of a road, including the ids of the starting city i and the destination city j, the distance l_ij and the condition d_ij. To simplify the input presentation we also assume that i < j so that a road will appear exactly once in the input. Each of the next p lines has the source and destination city pairs to compute the distance.

Output 

For each test case, output the length of the shortest route from the starting city to the destination city without going through two consecutive roads of the same condition for the p city pairs. If there are no feasible routes between a pair of cities, please output ``infinity''.

Sample Input 

2
5 5 3 5
1 2 1 1
2 3 100 2
3 4 100 3
4 5 1 1
2 4 1 2
1 4
1 5
2 4
2 5
3 5
5 5 2 5
1 2 1 1
2 3 100 2
3 4 100 2
4 5 500 1
2 4 1 1
1 4
1 5
2 4
2 5
3 5

Sample Output 

2
3
1
2
101
infinity
infinity
1
infinity
600

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define oo 100000000
using namespace std;
typedef struct {
    int x, y, l, k;
}Path;
Path Map[1001];
int cmp(const void *i, const void *j) {
    Path *x, *y;
    x = (Path *)i, y = (Path *)j;
    return x->x - y->x;
}
int min(int x, int y) {
    return x < y ? x : y;
}
int NodeL[51], NodeT[51];
int Queue[10000000];
void SPFA(int st, int ed, int n, int kind) {
    int i, j, k, l, Qt;
    int V[51][51], Cut = oo;
    for(i = 1; i <= n; i++)
        for(j = 0; j <= kind; j++)
            V[i][j] = oo;
    V[st][0] = 0, Queue[0] = st, Qt = 0;
    for(i = 0; i <= Qt; i++) {
        int tn = Queue[i];
        for(j = 0, k = NodeL[tn]; j < NodeT[tn]; j++, k++) {
            for(l = 0; l <= kind; l++)
                if(l != Map[k].k) {
                    if(V[Map[k].y][Map[k].k] > V[tn][l] + Map[k].l) {
                        V[Map[k].y][Map[k].k] = V[tn][l] + Map[k].l;
                        if(V[Map[k].y][Map[k].k] <= Cut)
                            Queue[++Qt] = Map[k].y;
                        if(Map[k].y == ed)
                            Cut = min(Cut, V[Map[k].y][Map[k].k]);
                    }
                }
        }
    }
    int Min = oo;
    for(i = 0; i <= kind; i++)
        Min = min(Min, V[ed][i]);
    if(Min == oo)
        printf("infinity\n");
    else
        printf("%d\n", Min);
}
int main() {
    int T, i, n, m, k, p;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d %d", &n, &m, &k, &p);
        for(i = 1; i <= n; i++)
            NodeL[i] = oo, NodeT[i] = 0;
        for(i = 0; i < m; i++) {
            scanf("%d %d %d %d", &Map[i].x, &Map[i].y, &Map[i].l, &Map[i].k);
            Map[i+m].x = Map[i].y;
            Map[i+m].y = Map[i].x;
            Map[i+m].l = Map[i].l;
            Map[i+m].k = Map[i].k;
        }
        m *= 2;
        qsort(Map, m, sizeof(Path), cmp);
        int st, ed;
        for(i = 0; i < m; i++) {
            NodeL[Map[i].x] = min(NodeL[Map[i].x], i);
            NodeT[Map[i].x]++;
        }
        while(p--) {
            scanf("%d %d", &st, &ed);
            SPFA(st, ed, n, k);
        }
    }
    return 0;
}