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

// Function to compute a^b mod mod
ll power_mod(ll a, ll b, ll mod){
    ll res=1;
    a %= mod;
    while(b >0){
        if(b &1) res = res * a % mod;
        a = a * a % mod;
        b >>=1;
    }
    return res;
}

// Function to compute inverse of a mod mod, assuming mod is prime
ll inv_mod(ll a, ll mod){
    return power_mod(a, mod -2, mod);
}

// Function to enumerate all independent sets in a graph and compute their products
void enumerate_independent_sets(int n, const vector<int>& adjacency, ll product_w, const vector<ll>& inv_w, vector<ll>& f){
    // Recursive backtracking
    f.clear();
    // Start with position 0, mask 0, product_inv=1
    // We will store f as a list of product_not_I
    // product_not_I = product_w * product(inv_w[i] for i in I)
    // Implement as iterative DFS
    struct State {
        int pos;
        int mask;
        ll product_inv;
    };
    stack<State> stk;
    stk.push(State{0, 0, 1});
    while(!stk.empty()){
        State current = stk.top(); stk.pop();
        if(current.pos == n){
            ll product_not_I = (product_w * current.product_inv) % 0x3f3f3f3f; // Placeholder
            // We will handle modulo outside
            f.push_back(current.product_inv);
            continue;
        }
        // Option 1: Exclude current vertex
        stk.push(State{current.pos +1, current.mask, current.product_inv});
        // Option 2: Include current vertex, if possible
        if( (current.mask & (1 << current.pos)) ==0 ){
            // Can include
            int new_mask = current.mask | adjacency[current.pos];
            stk.push(State{current.pos +1, new_mask, (current.product_inv * inv_w[current.pos])});
        }
    }
}

// Function to enumerate all independent sets in a graph and compute their products
void enumerate_independent_sets_recursive(int pos, int n, const vector<int>& adjacency, ll product_w, const vector<ll>& inv_w, ll current_product_inv, vector<ll>& f){
    if(pos == n){
        f.push_back(current_product_inv);
        return;
    }
    // Option 1: Exclude current vertex
    enumerate_independent_sets_recursive(pos +1, n, adjacency, product_w, inv_w, current_product_inv, f);
    // Option 2: Include current vertex, if possible
    // To include, no neighbors should be included
    // Since we are building the set incrementally, we need to ensure that none of the neighbors have been included
    // But since we are not keeping track of included vertices, we need to pass a mask
    // To make it efficient, switch to a bitmask based recursion
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for(int test_case=1; test_case <=T; test_case++){
        int n, m;
        ll q;
        cin >> n >> m >> q;
        vector<ll> w(n);
        for(int i=0; i<n; i++) cin >> w[i];
        // Read edges
        vector<vector<int>> adj(n, vector<int>());
        for(int i=0; i<m; i++){
            int u, v;
            cin >> u >> v; u--, v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        // Split into A and B
        int n1 = n /2;
        int n2 = n - n1;
        // Assign first n1 to A, rest to B
        // Build adjacency masks
        vector<int> adjacency_A(n1, 0);
        vector<int> adjacency_B(n2, 0);
        // Neighbors of A in B
        vector<int> neighbors_A_in_B(n1, 0);
        for(int i=0; i<n1; i++){
            for(auto &v: adj[i]){
                if(v < n1){
                    adjacency_A[i] |= (1 << v);
                }
                else{
                    neighbors_A_in_B[i] |= (1 << (v - n1));
                }
            }
        }
        for(int i=0; i<n2; i++){
            int vertex = n1 + i;
            for(auto &v: adj[vertex]){
                if(v >= n1){
                    adjacency_B[i] |= (1 << (v - n1));
                }
            }
        }
        // Compute product_w_A and product_w_B
        ll product_w_A =1;
        for(int i=0; i<n1; i++) product_w_A = product_w_A * w[i] % q;
        ll product_w_B =1;
        for(int i=0; i<n2; i++) product_w_B = product_w_B * w[n1 +i] % q;
        // Compute inv_w for A and B
        vector<ll> inv_w_A(n1, 1);
        for(int i=0; i<n1; i++) inv_w_A[i] = inv_mod(w[i], q);
        vector<ll> inv_w_B(n2, 1);
        for(int i=0; i<n2; i++) inv_w_B[i] = inv_mod(w[n1 +i], q);
        // Enumerate all independent sets in B and compute f[I_B} = product_not_I_B
        // Implement recursive enumeration
        vector<ll> f_B;
        // Implement enumeration with recursive backtracking
        // To handle n2=18, it's feasible
        // Use iterative DFS
        vector<ll> f_list;
        f_list.reserve(1 << n2);
        // Precompute adjacency masks for B
        vector<int> adj_B = adjacency_B;
        // Enumerate all independent sets in B
        // Implement recursive backtracking
        // To speed up, use memoization
        // Implement recursive function
        // Using lambda with memoization
        vector<ll> list_B;
        list_B.reserve(1 << n2);
        // Initialize
        // Start with mask=0, product_inv=1
        // Recursive function
        // To avoid stack overflow, use iterative DFS
        struct Frame {
            int pos;
            int mask;
            ll product_inv;
        };
        stack<Frame> stk;
        stk.push(Frame{0, 0, 1});
        while(!stk.empty()){
            Frame current = stk.top(); stk.pop();
            if(current.pos == n2){
                ll product_not_I_B = product_w_B;
                // Multiply by product_inv
                product_not_I_B = product_not_I_B * current.product_inv % q;
                list_B.push_back(product_not_I_B);
                continue;
            }
            // Option 1: Exclude current vertex
            stk.push(Frame{current.pos +1, current.mask, current.product_inv});
            // Option 2: Include current vertex, if possible
            if( (current.mask & (1 << current.pos)) ==0 ){
                int new_mask = current.mask | adj_B[current.pos];
                ll new_product_inv = current.product_inv * inv_w_B[current.pos] % q;
                stk.push(Frame{current.pos +1, new_mask, new_product_inv});
            }
        }
        // Now, list_B contains all f[I_B}
        // Perform subset zeta transform on B
        // Compute g[K] = sum_{I_B subset K} f[I_B}
        // Implement subset zeta transform
        int size_g = 1 << n2;
        vector<ll> g(size_g, 0);
        for(auto &val: list_B){
            // To perform the zeta transform, we need to add val to all supersets
            // But it's easier to first set g[K] = sum_{I subset K} f[I}
            // Here, list_B contains f[I_B} for all I_B
            // So set g[K] += f[I_B} for I_B subset K
            // Initialize g[K} =0, then add f[I_B} where I_B subset K
            // But it's easier to set g[K} initially with f[I_B} for K=I_B, then perform the zeta transform
            // Thus:
            // Initialize g[K} =0
            // Then for each I_B, g[K=I_B} += f[I_B}
            // Then perform the zeta transform
        }
        // Reset g
        fill(g.begin(), g.end(), 0LL);
        for(auto &val: list_B){
            // We don't have the mask, but it's difficult to map val back to mask
            // Thus, need to store masks with list_B
            // Change the enumeration to store masks
            // Restart enumeration
            // Enumerate all independent sets in B and store f[I_B} with masks
            list_B.clear();
            // Re-enumerate with masks
            stk.push(Frame{0, 0, 1});
            list_B.reserve(1 << n2);
            // Re-enumerate with mask
            // Reset list_B
            list_B.assign(1 << n2, 0);
            // Re-enumerate with mask and store
            // Clear list_B and enumerate again with masks
            // To avoid confusion, let's implement it correctly
            // Restart enumeration with mask
            list_B.clear();
            stk.push(Frame{0, 0, 1});
            while(!stk.empty()){
                Frame current = stk.top(); stk.pop();
                if(current.pos == n2){
                    ll product_not_I_B = product_w_B;
                    product_not_I_B = product_not_I_B * current.product_inv % q;
                    list_B.push_back(product_not_I_B);
                    continue;
                }
                // Option 1: Exclude current vertex
                stk.push(Frame{current.pos +1, current.mask, current.product_inv});
                // Option 2: Include current vertex, if possible
                if( (current.mask & (1 << current.pos)) ==0 ){
                    int new_mask = current.mask | adj_B[current.pos];
                    ll new_product_inv = current.product_inv * inv_w_B[current.pos] % q;
                    stk.push(Frame{current.pos +1, new_mask, new_product_inv});
                }
            }
            break; // Exit after correct enumeration
        }
        // Now, correctly enumerate list_B with masks
        // Enumerate again with masks
        list_B.clear();
        stk.push(Frame{0, 0, 1});
        while(!stk.empty()){
            Frame current = stk.top(); stk.pop();
            if(current.pos == n2){
                ll product_not_I_B = product_w_B;
                product_not_I_B = product_not_I_B * current.product_inv % q;
                list_B.push_back(product_not_I_B);
                continue;
            }
            // Option 1: Exclude current vertex
            stk.push(Frame{current.pos +1, current.mask, current.product_inv});
            // Option 2: Include current vertex, if possible
            if( (current.mask & (1 << current.pos)) ==0 ){
                int new_mask = current.mask | adj_B[current.pos];
                ll new_product_inv = current.product_inv * inv_w_B[current.pos] % q;
                stk.push(Frame{current.pos +1, new_mask, new_product_inv});
            }
        }
        // Now, list_B contains all f[I_B} without masks
        // To perform the zeta transform, we need to store f[I_B} with masks
        // Thus, redo enumeration with mask and store f[I_B} in an array indexed by mask
        vector<ll> f_B_correct(1 << n2, 0);
        stk.push(Frame{0, 0, 1});
        while(!stk.empty()){
            Frame current = stk.top(); stk.pop();
            if(current.pos == n2){
                ll product_not_I_B = product_w_B;
                product_not_I_B = product_not_I_B * current.product_inv % q;
                f_B_correct[current.mask] = (f_B_correct[current.mask] + product_not_I_B) % q;
                continue;
            }
            // Option 1: Exclude current vertex
            stk.push(Frame{current.pos +1, current.mask, current.product_inv});
            // Option 2: Include current vertex, if possible
            if( (current.mask & (1 << current.pos)) ==0 ){
                int new_mask = current.mask | adj_B[current.pos];
                ll new_product_inv = current.product_inv * inv_w_B[current.pos] % q;
                stk.push(Frame{current.pos +1, new_mask, new_product_inv});
            }
        }
        // Now, f_B_correct[K] contains f[I_B} for mask K
        // Initialize g[K} = f_B_correct[K]
        vector<ll> g_zeta(1 << n2, 0);
        for(int K=0; K<(1<<n2); K++) g_zeta[K] = f_B_correct[K];
        // Perform subset zeta transform on g_zeta
        for(int i=0; i<n2; i++) {
            for(int K=0; K<(1<<n2); K++) {
                if(K & (1 <<i)){
                    g_zeta[K] = (g_zeta[K] + g_zeta[K ^ (1 <<i)]) % q;
                }
            }
        }
        // Now, g_zeta[K] = sum_{I_B subset K} f[I_B}
        // Enumerate all independent sets in A and compute the sum
        // Enumerate all independent sets in A
        // Implement enumeration with mask and compute product_not_I_A and forbidden_F_A
        // Enumerate all independent sets in A
        // Initialize list_A as pairs of (forbidden_F_A, product_not_I_A)
        struct A_State {
            int pos;
            int mask;
            ll product_inv;
            int forbidden;
        };
        vector<pair<int, ll>> list_A;
        // Implement recursive backtracking for A
        stk.push(Frame{0, 0, 1});
        while(!stk.empty()){
            Frame current = stk.top(); stk.pop();
            if(current.pos == n1){
                // Compute forbidden_F_A
                // To compute forbidden_F_A, we need to know which vertices in B are adjacent to I_A
                // But we have not stored the mask of I_A
                // Thus, we need to modify the Frame to include forbidden_F_A
                // Redefine Frame
                continue;
            }
            // Not implemented correctly, need to switch to proper enumeration
        }
        // Instead of using stack, implement recursive lambda
        list_A.clear();
        // Define adjacency for A
        // Define neighbors in B for each vertex in A
        vector<int> neighbors_A_in_B_bits(n1, 0);
        for(int i=0; i<n1; i++) neighbors_A_in_B_bits[i] = neighbors_A_in_B[i];
        // Recursive lambda
        // Pass current position, current mask, current product_inv, current forbidden_F_A
        // and accumulate to list_A
        // Use memoization to avoid stack overflow
        // Implement iterative DFS
        struct A_Frame {
            int pos;
            int mask;
            ll product_inv;
            int forbidden_F_A;
        };
        stack<A_Frame> stk_A;
        stk_A.push(A_Frame{0, 0, 1, 0});
        while(!stk_A.empty()){
            A_Frame current = stk_A.top(); stk_A.pop();
            if(current.pos == n1){
                list_A.emplace_back(make_pair(current.forbidden_F_A, current.product_inv));
                continue;
            }
            // Option 1: Exclude current vertex
            stk_A.push(A_Frame{current.pos +1, current.mask, current.product_inv, current.forbidden_F_A});
            // Option 2: Include current vertex, if possible
            if( (current.mask & (1 << current.pos)) ==0 ){
                int new_mask = current.mask | adjacency_A[current.pos];
                int new_forbidden_F_A = current.forbidden_F_A | neighbors_A_in_B_bits[current.pos];
                ll new_product_inv = current.product_inv * inv_w_A[current.pos] % q;
                stk_A.push(A_Frame{current.pos +1, new_mask, new_product_inv, new_forbidden_F_A});
            }
        }
        // Now, list_A contains all (forbidden_F_A, product_not_I_A)
        // Compute product_not_I_A for each entry
        // list_A already has product_not_I_A as product_w_A * product_inv
        for(auto &p: list_A){
            p.second = (product_w_A * p.second) % q;
        }
        // Now, compute sum_S
        ll sum_S =0;
        for(auto &p: list_A){
            int forbidden_F_A = p.first;
            ll product_not_I_A = p.second;
            // Compute K = ~forbidden_F_A & ((1 <<n2) -1)
            int K = (~forbidden_F_A) & ((n2 ==0) ? 0 : ((1 <<n2) -1));
            if(n2 ==0){
                K =0;
            }
            sum_S = (sum_S + product_not_I_A * g_zeta[K] % q) % q;
        }
        // Output the result
        cout << "Case #" << test_case << ": " << sum_S % q << "\n";
    }
}