Little Cyan Fish는 수직선 위에 있습니다. 처음에 그는 위치 $a_0$에 있고, 그의 집은 위치 $0$에 있습니다.

그는 위치 $a_1, a_2, \ldots, a_n$을 이 순서대로 방문하고 싶어 합니다. 그는 수직선을 따라 어느 방향으로든 걸어갈 수 있습니다. 또한 언제든지 집으로 순간이동하거나, 집을 현재 자신이 있는 위치로 옮길 수 있습니다. 두 행동 모두 비용이 들지 않으며, 걷는 도중을 포함하여 원하는 만큼 여러 번 수행할 수 있습니다.

주어진 순서대로 모든 위치를 방문하기 위해 그가 걸어야 하는 최소 총 거리를 구하세요.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T$)가 하나 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 방문해야 할 위치의 개수를 나타내는 정수 $n$ ($1 \le n \le 5 \times 10^5$)이 하나 주어집니다. 두 번째 줄에는 초기 위치와 방문해야 할 위치들을 나타내는 $n + 1$개의 정수 $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$)이 주어집니다.

모든 테스트 케이스에 걸쳐 $n$의 합은 $5 \times 10^5$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 한 줄에 하나의 정수로 Little Cyan Fish가 걸어야 하는 최소 총 거리를 출력합니다.

예제

입력 1

4
1
7 0
2
0 10 5
3
0 4 2 0
3
-2 3 -2 3

출력 1

0
10
6
8

참고

첫 번째 예제 테스트 케이스에서, Little Cyan Fish는 위치 $0$에 있는 집으로 순간이동하므로 걸을 필요가 없습니다.

두 번째 예제 테스트 케이스에서, 그는 $0$에서 $10$까지 걸어가며 도중에 집을 위치 $5$로 옮깁니다. 그다음 위치 $5$로 순간이동합니다. 총 이동 거리는 $10$입니다.

세 번째 예제 테스트 케이스에서, 그는 $0$에서 $4$까지 걸어가며 도중에 집을 위치 $2$로 옮깁니다. 그다음 $2$로 순간이동한 뒤 $0$까지 걸어갑니다. 총 이동 거리는 $4 + 2 = 6$입니다.

네 번째 예제 테스트 케이스에서, 그는 $0$으로 순간이동한 뒤 $3$까지 걸어가고, 집을 $3$으로 옮깁니다. 그다음 $-2$까지 걸어간 뒤 $3$으로 순간이동합니다. 총 이동 거리는 $3 + 5 = 8$입니다.