Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

日本的貴族學校「Agnes」要來台開設分校了！

這間在日本以優秀研究成果享譽國際的大學，五年前在Agnes學園校長DE（學園高層充滿著不為人知的機密，故校長的名稱用神秘的代號DE稱之）熟嫻的外交手段經營下，向業界招募了五年五千億的大筆資金，並在極短的時間內超英趕美，登上全世界大學的TOP10。

在經過多年考核後，董事會決定在台灣設立國外第一所分校，台大校長在聽聞此消息後，準備從今年高中生中挑出間諜，潛入該學校收集情報，而你就是那位被挑中的天才高中生。

為了確保你可以通過「Agnes」的入學考試（雖然你是台灣最天才的高中生，但是要面對世界各地的高中生仍是一件不容易的事情！），台大派出校園內馬尾綁最好的學妹向「Agnes」的教學長蜜蜂騙取得了入學考試的題目（沒想到教學長喜歡馬尾女孩的傳聞是真的！）。

在看過入學考試的題目後，你對於拿滿分非常有自信，但為了降低間諜任務失敗的機率（任務失敗你就…嘿嘿嘿…），你決定在考前事先研究出計算該題目最快的方法（因為答案實在太難記了）。

以下便是「Agnes」的入學考試題目：

聰明的你很快就發現了幾件重要的事實：

1.     A矩陣的Column數目一定要等於B矩陣的Row數目才可以做∮運算。

2.     C矩陣的大小一定會是Row(A)*Column(B)，也就是Row(C)=Row(A)且Column(C)=Column(B)。

3.     彼彼運算需要大量的計算時間，計算一次C=∮（A,B）需要
Row(A)* Column(A)*Column(B) 個彼彼運算。

4.     要計算超過2個以上的tera operation時，依照不同的順序會需要不同的彼彼運算次數。

例如：要計算A∮B∮C的話，有兩種選擇：

（(A∮B) ∮C） 或者 (A∮(B∮C))。

假設A是7x10的矩陣，B是10x22的矩陣，C是22x37的矩陣，則

(A∮B) ∮C需要(7*10*22) + (7*22*37) = 7238次彼彼運算

A∮(B∮C) 需要(10*22*37)+(7*10*37) = 10730次彼彼運算

5.     雖然利用其它的特殊技巧可以更快速的計算出答案，但為了防止自己算錯，你決定只利用添加括號的方式來加快運算速度（也就是改變運算的順序）。

根據你不平凡的智力，計算500次彼彼運算需要一張A4白紙，因此一張雙面A4總共可計算1000次，因為此次入學考試由正直的DE親自監考，正直的DE常常懷疑學生不正直，故你最好事先計算出最低所需的計算紙數量，以免當天考試因為帶太多計算紙而被正直的DE懷疑你的身份！

輸入檔以一個數字T為開頭，代表題目卷共有T個小題（1<=T<=5）。

每個小題以一個整數N（1<=N<= 1000），代表有幾個矩陣需要做運算，接著有N行輸入，R_i和C_i分別代表矩陣A_i的Row及Column大小（1<=R_i<=1000， 1<=C_i<=1000，1<=i<=N）。

對每一組小題，你應該輸出一個非負整數H，代表若單獨計算該小題最少需要幾張計算紙，且在最後一行輸出整場考試最少需使用幾張計算紙。

2
3
7 10
10 22
22 37
6
30 35
35 15
15 5
5 10
10 20
20 25

8
16
23