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

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 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
W3sicHJvYmxlbV9pZCI6IjUwNTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ZmNcdWNjMjhcdWM3NTggXHVjMmUwIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BhcmtpbmcucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjE0OXB4OyB3aWR0aDoxNDdweFwiIFwvPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMxZmNcdWQ1NTFcdWQ1NThcdWI3ZWMgXHVhZTM0IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWM3OTBcdWM4ZmMgXHVhYzA0XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjOGZjXHVjYzI4XHViOTdjIFx1YzEzOFx1YzBjMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUmbmJzcDtcdWFkYzBcdWNjMmVcdWM1NDQgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNTQ0XHViYjM0XHViMzcwXHViMDk4IFx1YzhmY1x1Y2MyOFx1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1YzhmY1x1Y2MyOFx1Yjk3YyBcdWQ1NWMgXHVkNmM0XHVjNWQwXHViMjk0IFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1ODhcdWIzNTggXHVjMGMxXHVjODEwXHVjNzNjXHViODVjIFx1YWM3OFx1YzViNCBcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjI5MCBcdWIwYTAsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIyZTRcdWI5YWNcdWFjMDAgXHViMTA4XHViYjM0IFx1YzU0NFx1ZDMwY1x1YzExYyBcdWJjZDFcdWM2ZDBcdWM1ZDAgXHVhYzE0XHViMmU0LiBcdWM3NThcdWMwYWNcdWIyOTQgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNWQwXHVhYzhjIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM4NzBcdWFlMDggXHVhYzc3XHVhYzcwXHViMDk4LCBcdWMxZmNcdWQ1NTFcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YjlkMFx1Yjc3Y1x1YWNlMCBcdWQ1ODhcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMxZmNcdWQ1NTFcdWM3NDQgXHViYzg0XHViOWI0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YWRmOFx1YjE0MFx1Yzc1OCBcdWQyYjlcdWFlMzBcdWI5N2MgXHViYzFjXHVkNzE4XHVkNTc0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHVjOGZjXHVjYzI4IFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMzQgXHViM2M0XHViODVjXHViMjk0IFx1Yzc3Y1x1YzljMVx1YzEyMFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWJhYThcdWI0ZTAgXHVjMGMxXHVjODEwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzhmY1x1Y2MyOFx1YzdhNVx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4IFx1Yzg4Y1x1ZDQ1Y1x1YjljOFx1YjJlNCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWMxMjBcdWM2MDFcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0IFx1ZDU2ZFx1YzBjMSBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM4ZmNcdWNjMjhcdWJlNDRcdWI5N2MgXHVjNTQ0XHViMDdjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWMxZmNcdWQ1NTFcdWM3NDQgXHViOWM4XHVjZTU4XHVhZTMwIFx1YzgwNCBcdWFlNGNcdWM5YzBcdWIyOTQgXHVjOGZjXHVjYzI4XHVkNTVjIFx1Y2MyOFx1Yjk3YyBcdWM3NzRcdWIzZDlcdWMyZGNcdWQwYTRcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1ZDc5OFx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVjMTM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzFmY1x1ZDU1MVx1ZDU1YyBcdWJiM2NcdWFjNzRcdWM3NDQgXHViYWE4XHViNDUwIFx1YjRlNFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gXHVhYzAwXHViODI0XHVhY2UwIFx1YWNjNFx1ZDY4ZFx1ZDU1YyBcdWMwYzFcdWM4MTBcdWM3NDAgXHViYWE4XHViNDUwIFx1YmMyOVx1YmIzOFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IHRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IHQgJmxlOyAxMDApIFx1YmFhOFx1YjRlMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViYzI5XHViYjM4XHVkNTYwIFx1YzBjMVx1YzgxMFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgKDEgJmxlOyBuICZsZTsgMjApLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YzgxMFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IHhpICZsZTsgOTkpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1ODhcdWIzNTggXHViYWE4XHViNGUwIFx1YzBjMVx1YzgxMFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWFjZTAgXHVjYzI4XHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhYzc4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1MDU0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT3B0aW1hbCBQYXJraW5nIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BhcmtpbmcucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjE0OXB4OyB3aWR0aDoxNDdweFwiIFwvPldoZW4gc2hvcHBpbmcgb24gTG9uZyBTdHJlZXQsIE1pY2hhZWwgdXN1YWxseSBwYXJrcyBoaXMgY2FyIGF0IHNvbWUgcmFuZG9tIGxvY2F0aW9uLCBhbmQgdGhlbiB3YWxrcyB0byB0aGUgc3RvcmVzIGhlIG5lZWRzLiBDYW4geW91IGhlbHAgTWljaGFlbCBjaG9vc2UgYSBwbGFjZSB0byBwYXJrIHdoaWNoIG1pbmltaXNlcyB0aGUgZGlzdGFuY2UgaGUgbmVlZHMgdG8gd2FsayBvbiBoaXMgc2hvcHBpbmcgcm91bmQ/PFwvcD5cclxuXHJcbjxwPkxvbmcgU3RyZWV0IGlzIGEgc3RyYWlnaHQgbGluZSwgd2hlcmUgYWxsIHBvc2l0aW9ucyBhcmUgaW50ZWdlci4gWW91IHBheSBmb3IgcGFya2luZyBpbiBhIHNwZWNpXHVmYjAxYyBzbG90LCB3aGljaCBpcyBhbiBpbnRlZ2VyIHBvc2l0aW9uIG9uIExvbmcgU3RyZWV0LiBNaWNoYWVsIGRvZXMgbm90IHdhbnQgdG8gcGF5IGZvciBtb3JlIHRoYW4gb25lIHBhcmtpbmcgdGhvdWdoLiBIZSBpcyB2ZXJ5IHN0cm9uZywgYW5kIGRvZXMgbm90IG1pbmQgY2FycnlpbmcgYWxsIHRoZSBiYWdzIGFyb3VuZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGdpdmVzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgMSAmbGU7IHQgJmxlOyAxMDAuIFRoZXJlIGFyZSB0d28gbGluZXMgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgZmlyc3QgZ2l2ZXMgdGhlIG51bWJlciBvZiBzdG9yZXMgTWljaGFlbCB3YW50cyB0byB2aXNpdCwgMSAmbGU7IG4gJmxlOyAyMCwgYW5kIHRoZSBzZWNvbmQgZ2l2ZXMgdGhlaXIgbiBpbnRlZ2VyIHBvc2l0aW9ucyBvbiBMb25nIFN0cmVldCwgMCAmbGU7IHhpICZsZTsgOTkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGZvciBlYWNoIHRlc3QgY2FzZSBhIGxpbmUgd2l0aCB0aGUgbWluaW1hbCBkaXN0YW5jZSBNaWNoYWVsIG11c3Qgd2FsayBnaXZlbiBvcHRpbWFsIHBhcmtpbmcuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==