#include <iostream>
#include<vector>
using namespace std;
void dfs(int i, vector< vector<int> > adj, bool visited[], int dis[], 
                                      int low[], int parent[], bool ap[]){
                                          
    static int d =0;
    visited[i] = 1;
    int child = 0;
    dis[i] = low[i] = ++d;
    for(int j = 0;j < adj[i].size();j++){
       // cout<<"hey"<<" ";
       if(visited[adj[i][j]] == 0){
           child++;
           parent[adj[i][j]] = i;
           dfs(adj[i][j],adj,visited,dis,low,parent,ap);
           low[i] = min(low[i],low[adj[i][j]]);
           if(parent[i] == i && child>1){
               ap[i] = true;
           }
           if( parent[i] != i && low[adj[i][j]] >= dis[i]){
               ap[i] = true;
           }
       } 
       else{
           if(adj[i][j] != parent[i]){
               low[i] = min(low[i],dis[adj[i][j]]);
           }
       }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test;
    cin>>test;
    while(test--){
        int n,m,k;
        cin>>n>>m>>k;
       // cout<<"hey"<<endl;
         bool *visited = new bool[n];
         int *dis = new int[n];
          int *low = new int[n];
         int *parent = new int[n];
         bool *ap = new bool[n];
        for(int i = 0;i < n;i++){
            parent[i] = i;
            dis[i] = 0;
            low[i] = 0;
            ap[i]= false;
            visited[i] = 0;
        }
        vector <vector <int> > adj(n+1,vector<int>());
        for(int i = 0; i < m;i++){
           int x,y;
           cin>>x>>y;
           adj[x].push_back(y);
           adj[y].push_back(x);
        }
        if(m == n*(n-1)/2){
           cout<<"0"<<endl;
           continue;
        } 
        int cnt = 0;
        dfs(0,adj,visited,dis,low,parent,ap);
        for(int i = 0; i < n;i++){
            if(ap[i] == true){
               // cout<<"hey"<<endl;
                cnt++;
            }
        }
        //cout<<cnt<<endl;
        cout<<cnt*k<<endl;
    }
	return 0;
}