#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define lld long double
#define nodecnt 100005
#define INF (1<<20)
#define mod 1000000007
inline lli scan( )
{
register lli n1 = 0;
char c;
for( c = getchar_unlocked(); c==' ' || c=='\n' || c == '\t'; c = getchar_unlocked());
for( ; c > 0x2f && c < 0x3a; c = getchar_unlocked())
n1 = (n1 * 10) + (c & 0x0f);
return n1;
}
lld key[nodecnt],x,y;
std::vector<pair<lld,lld> > cord;
bool donewith[nodecnt];
lli nodes,edges,start,dest,p,ans;
std::vector<pair<lli,lli> > graph[nodecnt] ;
lld eucdist(lli i,lli j)
{
return ceil(p*sqrt(((cord[i].first-cord[j].first)*(cord[i].first-cord[j].first))+((cord[i].second-cord[j].second)*(cord[i].second-cord[j].second))));
}
void prims()
{
ans=0;
set<pair<lld,lli> > Q;
for(lli i=1;i<=nodes;i++)
key[i]=INF,donewith[i]=false,Q.insert(make_pair(key[i],i));
Q.erase(Q.find(make_pair(key[start],start)));
key[start]=0;
Q.insert(make_pair(key[start],start));
while(!Q.empty())
{
pair<lld,lli> top=*(Q.begin());
Q.erase(Q.begin());
lli u=top.second;
donewith[u]=true;
if(u!=start)
{
ans+=top.first;
if(ans>=mod)
ans=ans%mod;
}
lli size=graph[u].size();
for(lli i=0;i<size;i++)
{
lli v=graph[u][i].first;
lld w=graph[u][i].second;
if(donewith[v]==false)
{
if(key[v]>w)
{
Q.erase(Q.find(make_pair(key[v],v)));
key[v]=w;
Q.insert(make_pair(key[v],v));
}
}
}
}
}
int main(int argc, char const *argv[])
{
lli t;
t=scan();
for(lli T=1;T<=t;T++)
{
nodes=scan(),p=scan();
for(lli i=1;i<=nodes;i++)
graph[i].clear();
cord.clear();
cord.push_back(make_pair(INF,INF));
for(lli i=1;i<=nodes;i++)
x=scan(),y=scan(),cord.push_back(make_pair(x,y));
sort(cord.begin()+1,cord.end());
for(lli i=1;i<nodes;i++)
{
lld temp=eucdist(i+1,i);
graph[i].push_back(make_pair(i+1,temp));
graph[i+1].push_back(make_pair(i,temp));
for(lli j=i+2;j<=nodes;j++)
{
lld temp=eucdist(i,j);
if(temp<=eucdist(j,j-1)+eucdist(j-1,i))
{
graph[i].push_back(make_pair(j,temp));
graph[j].push_back(make_pair(i,temp));
}
}
}
start=1,ans=0;
prims();
printf("Scenario #%lld: %lld\n",T,ans);
}
return 0;
}
CSNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgoJdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCSNkZWZpbmUgbGxpIGxvbmcgbG9uZyBpbnQKCSNkZWZpbmUgbGxkIGxvbmcgZG91YmxlCgkjZGVmaW5lIG5vZGVjbnQgMTAwMDA1CgkjZGVmaW5lIElORiAoMTw8MjApCgkjZGVmaW5lIG1vZCAxMDAwMDAwMDA3CglpbmxpbmUgbGxpIHNjYW4oICkKCXsKCQlyZWdpc3RlciBsbGkgbjEgPSAwOwoJCWNoYXIgYzsKCQlmb3IoIGMgPSBnZXRjaGFyX3VubG9ja2VkKCk7IGM9PScgJyB8fCBjPT0nXG4nIHx8IGMgPT0gJ1x0JzsgYyA9IGdldGNoYXJfdW5sb2NrZWQoKSk7CgkJZm9yKCA7IGMgPiAweDJmICYmIGMgPCAweDNhOyBjID0gZ2V0Y2hhcl91bmxvY2tlZCgpKQoJCW4xID0gKG4xICogMTApICsgKGMgJiAweDBmKTsKCQlyZXR1cm4gbjE7Cgl9CglsbGQga2V5W25vZGVjbnRdLHgseTsKCXN0ZDo6dmVjdG9yPHBhaXI8bGxkLGxsZD4gPiBjb3JkOwoJYm9vbCBkb25ld2l0aFtub2RlY250XTsKCWxsaSBub2RlcyxlZGdlcyxzdGFydCxkZXN0LHAsYW5zOwoJc3RkOjp2ZWN0b3I8cGFpcjxsbGksbGxpPiA+IGdyYXBoW25vZGVjbnRdIDsKCWxsZCBldWNkaXN0KGxsaSBpLGxsaSBqKQoJewoJCXJldHVybiBjZWlsKHAqc3FydCgoKGNvcmRbaV0uZmlyc3QtY29yZFtqXS5maXJzdCkqKGNvcmRbaV0uZmlyc3QtY29yZFtqXS5maXJzdCkpKygoY29yZFtpXS5zZWNvbmQtY29yZFtqXS5zZWNvbmQpKihjb3JkW2ldLnNlY29uZC1jb3JkW2pdLnNlY29uZCkpKSk7Cgl9Cgl2b2lkIHByaW1zKCkKCXsKCQlhbnM9MDsKCQlzZXQ8cGFpcjxsbGQsbGxpPiA+IFE7CgkJZm9yKGxsaSBpPTE7aTw9bm9kZXM7aSsrKQoJCQlrZXlbaV09SU5GLGRvbmV3aXRoW2ldPWZhbHNlLFEuaW5zZXJ0KG1ha2VfcGFpcihrZXlbaV0saSkpOwoJCQkKCQlRLmVyYXNlKFEuZmluZChtYWtlX3BhaXIoa2V5W3N0YXJ0XSxzdGFydCkpKTsKCQlrZXlbc3RhcnRdPTA7CgoJCVEuaW5zZXJ0KG1ha2VfcGFpcihrZXlbc3RhcnRdLHN0YXJ0KSk7CgkJd2hpbGUoIVEuZW1wdHkoKSkKCQl7CgkJCXBhaXI8bGxkLGxsaT4gdG9wPSooUS5iZWdpbigpKTsKCQkJUS5lcmFzZShRLmJlZ2luKCkpOwoJCQlsbGkgdT10b3Auc2Vjb25kOwoJCQlkb25ld2l0aFt1XT10cnVlOwoJCQlpZih1IT1zdGFydCkKCQkJewoJCQkJYW5zKz10b3AuZmlyc3Q7CgkJCQlpZihhbnM+PW1vZCkKCQkJCQlhbnM9YW5zJW1vZDsKCQkJfQkJCgkJCWxsaSBzaXplPWdyYXBoW3VdLnNpemUoKTsKCQkJZm9yKGxsaSBpPTA7aTxzaXplO2krKykKCQkJewoJCQkJbGxpIHY9Z3JhcGhbdV1baV0uZmlyc3Q7CgkJCQlsbGQgdz1ncmFwaFt1XVtpXS5zZWNvbmQ7CgkJCQlpZihkb25ld2l0aFt2XT09ZmFsc2UpCgkJCQl7CQoJCQkJCWlmKGtleVt2XT53KQoJCQkJCXsKCQkJCQkJUS5lcmFzZShRLmZpbmQobWFrZV9wYWlyKGtleVt2XSx2KSkpOwoJCQkJCQlrZXlbdl09dzsKCQkJCQkJUS5pbnNlcnQobWFrZV9wYWlyKGtleVt2XSx2KSk7CgkJCQkJfQoJCQkJfQoJCQl9CgkJfQoJfQoJaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgY29uc3QgKmFyZ3ZbXSkKCXsKCQlsbGkgdDsKCQl0PXNjYW4oKTsKCQlmb3IobGxpIFQ9MTtUPD10O1QrKykKCQl7CgkJCW5vZGVzPXNjYW4oKSxwPXNjYW4oKTsKCQkJZm9yKGxsaSBpPTE7aTw9bm9kZXM7aSsrKQoJCQkJZ3JhcGhbaV0uY2xlYXIoKTsKCQkJY29yZC5jbGVhcigpOwoJCQljb3JkLnB1c2hfYmFjayhtYWtlX3BhaXIoSU5GLElORikpOwoJCQlmb3IobGxpIGk9MTtpPD1ub2RlcztpKyspCgkJCQl4PXNjYW4oKSx5PXNjYW4oKSxjb3JkLnB1c2hfYmFjayhtYWtlX3BhaXIoeCx5KSk7CgkJCXNvcnQoY29yZC5iZWdpbigpKzEsY29yZC5lbmQoKSk7CgkJCWZvcihsbGkgaT0xO2k8bm9kZXM7aSsrKQoJCQl7CgkJCQlsbGQgdGVtcD1ldWNkaXN0KGkrMSxpKTsKCQkJCWdyYXBoW2ldLnB1c2hfYmFjayhtYWtlX3BhaXIoaSsxLHRlbXApKTsKCQkJCWdyYXBoW2krMV0ucHVzaF9iYWNrKG1ha2VfcGFpcihpLHRlbXApKTsKCQkJCWZvcihsbGkgaj1pKzI7ajw9bm9kZXM7aisrKQoJCQkJewoJCQkJCWxsZCB0ZW1wPWV1Y2Rpc3QoaSxqKTsKCQkJCQlpZih0ZW1wPD1ldWNkaXN0KGosai0xKStldWNkaXN0KGotMSxpKSkKCQkJCQl7CQoJCQkJCQlncmFwaFtpXS5wdXNoX2JhY2sobWFrZV9wYWlyKGosdGVtcCkpOwoJCQkJCQlncmFwaFtqXS5wdXNoX2JhY2sobWFrZV9wYWlyKGksdGVtcCkpOwoJCQkJCX0KCQkJCX0KCQkJfQoJCQlzdGFydD0xLGFucz0wOwoJCQlwcmltcygpOwoJCQlwcmludGYoIlNjZW5hcmlvICMlbGxkOiAlbGxkXG4iLFQsYW5zKTsKCQl9CgkJcmV0dXJuIDA7Cgl9CQ==