시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1027 822 768 81.876%

문제

선영이는 쇼핑하러 긴 도로에 자주 간다. 선영이는 주차를 세상에서 가장 귀찮아 하기 때문에, 아무데나 주차를 한다. 주차를 한 후에는 가려고 했던 상점으로 걸어 간다.

어느날, 선영이는 다리가 너무 아파서 병원에 갔다. 의사는 선영이에게 되도록 조금 걷거나, 쇼핑을 하지 말라고 했다. 선영이는 쇼핑을 버릴 수 없다. 그녀의 특기를 발휘해서 가장 좋은 주차 자리를 찾으려고 한다.

긴 도로는 일직선이다. 또, 모든 상점의 위치는 정수 좌표를 가지고 있다. 주차장은 모든 정수 좌표마다 하나씩 있으며, 선영이를 위해 항상 비어있다. 선영이는 주차비를 아끼기 위해서 쇼핑을 마치기 전 까지는 주차한 차를 이동시키지 않을 것이다. 선영이는 힘이 매우 세기 때문에, 자신이 쇼핑한 물건을 모두 들지 못하는 경우는 없다. 가려고 계획한 상점은 모두 방문해야 한다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 100) 모든 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 선영이가 방문할 상점의 수 n이 주어지며 (1 ≤ n ≤ 20), 둘째 줄에는 상점의 위치가 주어진다. (0 ≤ xi ≤ 99)

출력

선영이가 가려고 했던 모든 상점을 방문하고 차로 돌아오기 위해 걸어야 하는 거리의 최솟값을 출력한다. 

예제 입력 1

2
4
24 13 89 37
6
7 30 41 14 39 42

예제 출력 1

152
70
W3sicHJvYmxlbV9pZCI6IjUwNTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ZmNcdWNjMjhcdWM3NTggXHVjMmUwIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BhcmtpbmcucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjE0OXB4OyB3aWR0aDoxNDdweFwiIFwvPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMxZmNcdWQ1NTFcdWQ1NThcdWI3ZWMgXHVhZTM0IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWM3OTBcdWM4ZmMgXHVhYzA0XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjOGZjXHVjYzI4XHViOTdjIFx1YzEzOFx1YzBjMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUmbmJzcDtcdWFkYzBcdWNjMmVcdWM1NDQgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNTQ0XHViYjM0XHViMzcwXHViMDk4IFx1YzhmY1x1Y2MyOFx1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1YzhmY1x1Y2MyOFx1Yjk3YyBcdWQ1NWMgXHVkNmM0XHVjNWQwXHViMjk0IFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1ODhcdWIzNTggXHVjMGMxXHVjODEwXHVjNzNjXHViODVjIFx1YWM3OFx1YzViNCBcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjI5MFx1YjBhMCwgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjJlNFx1YjlhY1x1YWMwMCBcdWIxMDhcdWJiMzQgXHVjNTQ0XHVkMzBjXHVjMTFjIFx1YmNkMVx1YzZkMFx1YzVkMCBcdWFjMTRcdWIyZTQuIFx1Yzc1OFx1YzBhY1x1YjI5NCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHViNDE4XHViM2M0XHViODVkIFx1Yzg3MFx1YWUwOCBcdWFjNzdcdWFjNzBcdWIwOTgsIFx1YzFmY1x1ZDU1MVx1Yzc0NCBcdWQ1NThcdWM5YzAgXHViOWQwXHViNzdjXHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzFmY1x1ZDU1MVx1Yzc0NCBcdWJjODRcdWI5YjQgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVhZGY4XHViMTQwXHVjNzU4IFx1ZDJiOVx1YWUzMFx1Yjk3YyBcdWJjMWNcdWQ3MThcdWQ1NzRcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzg4Ylx1Yzc0MCBcdWM4ZmNcdWNjMjggXHVjNzkwXHViOWFjXHViOTdjIFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWUzNCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjNzdjXHVjOWMxXHVjMTIwXHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1YmFhOFx1YjRlMCBcdWMwYzFcdWM4MTBcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YzgxNVx1YzIxOCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjOGZjXHVjYzI4XHVjN2E1XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHViOWM4XHViMmU0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NzQgXHVkNTZkXHVjMGMxIFx1YmU0NFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzhmY1x1Y2MyOFx1YmU0NFx1Yjk3YyBcdWM1NDRcdWIwN2NcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzFmY1x1ZDU1MVx1Yzc0NCBcdWI5YzhcdWNlNThcdWFlMzAgXHVjODA0IFx1YWU0Y1x1YzljMFx1YjI5NCBcdWM4ZmNcdWNjMjhcdWQ1NWMgXHVjYzI4XHViOTdjIFx1Yzc3NFx1YjNkOVx1YzJkY1x1ZDBhNFx1YzljMCBcdWM1NGFcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVkNzk4XHVjNzc0IFx1YjllNFx1YzZiMCBcdWMxMzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjMWZjXHVkNTUxXHVkNTVjIFx1YmIzY1x1YWM3NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViNGU0XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWFjMDBcdWI4MjRcdWFjZTAgXHVhY2M0XHVkNjhkXHVkNTVjIFx1YzBjMVx1YzgxMFx1Yzc0MCBcdWJhYThcdWI0NTAgXHViYzI5XHViYjM4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgdCAmbGU7IDEwMCkgXHViYWE4XHViNGUwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMGMxXHVjODEwXHVjNzU4IFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCAoMSAmbGU7IG4gJmxlOyAyMCksIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVjODEwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgeGkgJmxlOyA5OSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVhYzAwXHViODI0XHVhY2UwIFx1ZDU4OFx1YjM1OCBcdWJhYThcdWI0ZTAgXHVjMGMxXHVjODEwXHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWNlMCBcdWNjMjhcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjNzhcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjUwNTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPcHRpbWFsIFBhcmtpbmciLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGFya2luZy5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTQ5cHg7IHdpZHRoOjE0N3B4XCIgXC8+V2hlbiBzaG9wcGluZyBvbiBMb25nIFN0cmVldCwgTWljaGFlbCB1c3VhbGx5IHBhcmtzIGhpcyBjYXIgYXQgc29tZSByYW5kb20gbG9jYXRpb24sIGFuZCB0aGVuIHdhbGtzIHRvIHRoZSBzdG9yZXMgaGUgbmVlZHMuIENhbiB5b3UgaGVscCBNaWNoYWVsIGNob29zZSBhIHBsYWNlIHRvIHBhcmsgd2hpY2ggbWluaW1pc2VzIHRoZSBkaXN0YW5jZSBoZSBuZWVkcyB0byB3YWxrIG9uIGhpcyBzaG9wcGluZyByb3VuZD88XC9wPlxyXG5cclxuPHA+TG9uZyBTdHJlZXQgaXMgYSBzdHJhaWdodCBsaW5lLCB3aGVyZSBhbGwgcG9zaXRpb25zIGFyZSBpbnRlZ2VyLiBZb3UgcGF5IGZvciBwYXJraW5nIGluIGEgc3BlY2lcdWZiMDFjIHNsb3QsIHdoaWNoIGlzIGFuIGludGVnZXIgcG9zaXRpb24gb24gTG9uZyBTdHJlZXQuIE1pY2hhZWwgZG9lcyBub3Qgd2FudCB0byBwYXkgZm9yIG1vcmUgdGhhbiBvbmUgcGFya2luZyB0aG91Z2guIEhlIGlzIHZlcnkgc3Ryb25nLCBhbmQgZG9lcyBub3QgbWluZCBjYXJyeWluZyBhbGwgdGhlIGJhZ3MgYXJvdW5kLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgZ2l2ZXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCAxICZsZTsgdCAmbGU7IDEwMC4gVGhlcmUgYXJlIHR3byBsaW5lcyBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBmaXJzdCBnaXZlcyB0aGUgbnVtYmVyIG9mIHN0b3JlcyBNaWNoYWVsIHdhbnRzIHRvIHZpc2l0LCAxICZsZTsgbiAmbGU7IDIwLCBhbmQgdGhlIHNlY29uZCBnaXZlcyB0aGVpciBuIGludGVnZXIgcG9zaXRpb25zIG9uIExvbmcgU3RyZWV0LCAwICZsZTsgeGkgJmxlOyA5OS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgZm9yIGVhY2ggdGVzdCBjYXNlIGEgbGluZSB3aXRoIHRoZSBtaW5pbWFsIGRpc3RhbmNlIE1pY2hhZWwgbXVzdCB3YWxrIGdpdmVuIG9wdGltYWwgcGFya2luZy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=