시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB28252589.286%

문제

Prince of Songkla University or PSU has 5 campuses in the South of Thailand. These campuses are Hatyai(H), Pattani(P), Suratthani(S), Phuket(K) and Trang(T). The distances between these campuses are shown in the table below. 

Campuses Distance (km) Campuses Distance (km)
Hatyai – Pattani 103 Pattani - Phuket 577
Hatyai – Suratthani 329 Pattani - Trang 260
Hatyai – Phuket 466 Suratthani - Phuket 287
Hatyai – Trang 148 Suratthani - Trang 226
Pattani – Suratthani 408 Phuket - Trang 312

When the President of PSU goes on mission in different campuses, he or she may want to know the total distance of the mission. The mission always starts from Hatyai campus and when the mission ends the president will always go back directly to Hatyai campus. 

Given a list of campuses of a mission, your task is to write a program to calculate the total distance of the mission. 

입력

The first line contains an integer n (1 ≤ n ≤ 100) which determines the number of missions. The following n lines contain a description of each mission. A mission is described by a string comprising only characters H, P, S, K and T which refer to PSU campuses. The president visits the campuses in the order indicated in that string. Since Hatyai campus is always the starting point and also the end point of a mission, we will not mention H at the beginning or the end of the string. However, H can be an intermediate campus in a mission. A mission string may contain at most 10 characters. 

출력

For each mission (missioni), print out in a line, “Case i: ” followed by the total distance (km), exactly as shown in the sample output. 

예제 입력 1

4
TSK
PHT
PSKT
KT

예제 출력 1

Case 1: 1127
Case 2: 502
Case 3: 1258
Case 4: 926