S93-CA2-2

Time Limit: 1 Second    Memory Limit: 65536 KB

E.Nigma

رابین در پارک مشغول جستجو بود که ناگهان در یکی از تله‌های ریدلر افتاد. ریدلر از این که شخص بتمن به دام وی نیفتاده ناراحت بود، به همین خاطر تصمیم گرفت سوال پیچیده‌ای به رابین بدهد تا نتواند آن را حل کند. معما به صورت زیر است:

    تعدادی (n) کارت در یک ردیف داریم. هر کدام از این کارت‌ها یک شماره‌ دارند، می‌خواهیم کارت‌ها را به ترتیبی از این ردیف برداریم. هر کارتی که بر می‌داریم امتیاز عدد آن کارت ضرب‌در عدد کارت سمت چپ ضر‌ب‌در عدد کارت سمت راست آن کارت را از دست می‌دهیم. هم‌چنین نمی‌توانیم کارت‌های ابتدا و انتها‌ی ردیف را برداریم. آن‌قدر کارت برمی‌داریم تا تنها ۲ کارت ابتدا و انتهایی باقی بماند. برای نمونه‌ی محاسبه‌ی امتیاز از دست رفته فرض کنید ۵ کارت با اعداد 5 , 6 , 10, 25, 1 داریم.

ترتیب انتخاب کارت

امتیازی که از دست می‌دهیم

6, 10, 25

5*6*10 + 5*10*25 + 5*25*1 = 1675

25, 10, 6

10*25*1 + 6*10*1 + 5*6*1 = 340

 

    ریدلر تعدادی کارت جلوی رابین می‌گذارد و از او می‌خواهد تا ترتیبی انتخاب کند که کمترین امتیاز را از دست بدهد. رابین که نمی‌تواند این مساله را حل کند از اوراکل کمک می‌خواهد تا جوابی پیدا کند. برای اوراکل برنامه‌ای بنویسید که ترتیبی پیدا کند تا مجموع امتیازی که رابین از دست می‌دهد کمینه شود.

 

Input

 در خط اول t < 30 می‌آید که تعداد مورد‌هایی است که برنامه‌ی شما باید پاسخ دهد، درخط اول هر مورد‌  n (کوچک‌تر مساوی ۱۰۰) تعداد کارت‌ها است. در خط بعدی، n عدد کوچکترمساوی ۱۰۰ می‌آید که نشان‌دهنده‌ی عدد کارت‌های ردیف است.

Output

برای هر مورد، کمینه‌ی امتیازی که از دست می‌رود را بنویسید.

Sample Input

2
5
5 6 10 25 1
6
10 1 50 50 20 5

Sample Output

340
3650
Submit