최적의 주차 (Optimal Parking)

선보는 정올 아울렛에서 쇼핑할 때 보통 임의의 위치에 차를 주차한 다음 필요한 매장으로 걸어간다.

정올 아울렛의 모든 매장은 직선상에 위치해 있기에 해당 위치를 정수로 표현 가능하다. 선보는 기름값을 아끼기 위해 주차한 차를 쇼핑을 마치기 전까진 이동시키지 않을 예정이다. 선보는 매우 강하기에 쇼핑백을 아무리 많이 들어도 괜찮다.

선보가 쇼핑을 하기 위해 걸어야 하는 거리를 최소화하는 주차 장소를 선택하도록 도와주자.

Input

첫 줄에 테스트 케이스의 수 t가 주어진다. (1 ≤ t ≤ 100)

모든 테스트 케이스는 두 줄로 이루어져 있다. 첫 줄에는 선보가 방문할 상점의 수 n이 주어지고, 두 번째 줄에는 각 매장의 위치 x_i가 주어진다. (1 ≤ n ≤ 20, 0 ≤ x_i ≤ 99)

Output

선보가 쇼핑을 하기 위해 걸어야 하는 최소 거리를 출력한다.

Example

Source

NCPC(Nordic Collegiate Programming Contest) 2007

최적의 주차 (Optimal Parking) 1s 1024MB