Circle Line

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

Input

 

Output

For each test case, print a single number — the length of the shortest path between stations number s and t.

Sample Input

4
2 3 4 9
1 3
4
5 8 2 100
4 1

Sample Output

5
15

Hint

 

Source

qinchuan