Саяхатшы Ергежейлі биылғы жылы өз назарын Вроцлав шыңдарын бағындыруға аударуды ұйғарды. Оның соңғы мақсаты — қатарынан $N$ күн ішінде әр күні дәл бір шыңнан, барлығы $N$ әртүрлі шыңды бағындыру. Шыңдарды бағындыру Саяхатшы үшін түкке тұрмайды. Ол кез келген күні кез келген шыңды бағындыра алады, сондықтан ол бүкіл экспедицияны бұқаралық ақпарат құралдарында мүмкіндігінше кеңінен жария етуді шешті.

Ергежейлі жақында белгілі бір заңдылықты байқады:

• Бірінші шыңды бағындырғаннан кейін, оның биіктігіне қарамастан, БАҚ қызығушылығы жоғары болады.
• Егер ол бір күні биіктігі $a$ болатын шыңды, ал келесі күні биіктігі $b$ болатын шыңды бағындырса, оның экспедициясына деген БАҚ қызығушылығы $\lfloor a/b \rfloor$ бірлікке кемиді, ол мұны БАҚ қызығушылығының бірліктері деп атайды.

Саяхатшы биіктіктері $a_1, \dots, a_N$ болатын $N$ шыңды бағындыруы керек екенін біледі. Сонымен қатар, ең биік шыңның биіктігі ең аласа шыңның биіктігінен ең көбі екі есе үлкен екені белгілі болды. Ергежейлі шыңдарды аралау ретін өз қалауынша таңдай алады. Оның мақсаты — бүкіл экспедиция барысында БАҚ қызығушылығы бірліктерінің жалпы кемуін барынша азайту.

БАҚ қызығушылығы бірліктерінің кемуі ең аз болатындай етіп, барлық шыңдарды аралау ретін таңдауға оған көмектесе аласыз ба?

Кіріс деректер

Кіріс деректердің бірінші жолында тест жағдайларының санын білдіретін $T$ саны берілген.

Әрбір тест жағдайының бірінші жолында Саяхатшы баратын шыңдар санын білдіретін бір бүтін сан $N$ берілген.

Тест жағдайының екінші жолында есеп шартын қанағаттандыратын $N$ бүтін сан $a_1, \dots, a_N$ берілген.

Шығыс деректер

Әрбір тест жағдайы үшін екі жол шығарыңыз. Бірінші жолда ергежейлінің саяхаты үшін БАҚ қызығушылығы бірліктерінің ең аз мүмкін кемуін білдіретін бір бүтін сан болуы керек.

Екінші жолда осы ең аз кемуге қол жеткізу үшін Ергежейлі аралауы тиіс ретпен орналасқан $a_1, \dots, a_N$ биіктіктері болуы керек.

Егер оңтайлы шешімдер бірнешеу болса, кез келгенін шығаруға болады.

Шектеулер

$1 \le T \le 100\,000, 1 \le N \le 10^6, 1 \le a_i \le 10^9, \max\{a_1, \dots, a_N\} \le 2 \cdot \min\{a_1, \dots, a_N\}$, кірісте берілген $N$ мәндерінің қосындысы $10^6$-нен аспайды.

Мысалдар

Кіріс деректер 1

3
6
10 18 12 13 17 14
4
10 10 7 7
8
8 4 8 5 4 4 8 6

Шығыс деректер 1

0
10 12 13 14 17 18
1
7 10 7 10
4
4 4 4 5 6 8 8 8