源 達博在一次的旅途中,在月亮山中迷了路,同時又因為他的提款卡鎖在櫃子裡,沒有帶出來,由於飢餓難耐,源 達博最後不支倒地。這時候路過的赤円円將他帶到円円族的部落,供吃供住,並且帶他離開月亮山。事後源 達博為了答謝円円們的幫助,準備了很多禮物要送給「他們的」。
源 達博現在已經準備好六種大小不同的禮物,其面積大小分別有:$1\times 1$ , $2\times 2$ , $3\times 3$ , $4\times 4$ , $5\times 5$ , $6\times 6$等六種尺寸,這些禮物高度皆為 $h$。而他的女秘書幫他準備好了面積為$6\times 6$的箱子,高度 $h$ 的正方形箱子用來放禮物。
物品中$N\times N$的那兩面都會印上商標,而側面則不會。源 達博為了表達他的誠意,他要求物品一定都要直放(如上圖),這樣子才能夠不管之後怎麼拿取都能看到商標。所以可以將物品及箱子視為在一個二維平面上。
由於成本關係,源 達博希望所有的禮物放在最少的箱子裡寄出。請你寫一個程式計算出贈送這些禮物最少需要多少個箱子,這可以替源 達博省下不少錢,讓他以後可以多包一點紅包。
輸入的第一行包含一個正整數 $T (T \leq 2400)$,代表測試資料的個數。每個測試資料一列(就是一次送禮),含有 $6$ 個整數(數字的範圍不超過$32767$)。分別代表 $1\times 1$ 到 $6\times 6$ 產品的數目。
對每一組測試資料,輸出贈送這些禮物最少需要多少個箱子。
範例輸入第一筆測試資料使用最少箱子的擺法,使用 $2$ 個箱子。
範例輸入第二筆測試資料使用最少箱子的擺法,使用 $1$ 個箱子。。
NEOJ Problem 78
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~9 | 100 |