到老舊的火車站你也許會遇到少數僅存的「車箱置換員」(train swapper)，車箱置換員是車站的員工，他的工作是重新排列火車車箱。

當每節車箱 (尤其是裝貨的車箱) 都經過適當的排列之後，火車司機在每個車站卸貨時只需從最後車箱一節一節依序放下即可。

「車箱置換員」的職稱起源於一座位於河畔的火車站，鐵路橫跨在河的兩岸，當船隻要通行時，橋上的鐵路不像其他地方一樣會垂直升起，而是以河中央的橋墩為中心旋轉 90 度，此時船隻可從橋的左右兩旁經過。

另外，首位車箱置換員發現一件有趣的事，當橋在作旋轉時最多可乘載兩節車箱的重量，所以當橋作 180 度的旋轉之後，其上的車箱就被掉換位置了，因此他就能重新排列車箱 (副作用就是車箱前後位置會相反，不過因為車箱被設計成可以前後移動，所以無所謂)。

現在幾乎所有車箱置換員都死光了，鐵路公司必須做車箱掉換的自動化，需要寫一個程式來計算共需置換相鄰的車箱幾次才能使所有車箱依序排好，寫程式的工作就交給你了。

Input Specification

第一列有一個整數表示接下來有 $N$ 組測試資料，每組測試資料兩列，第一列是一個整數 $L$ ($1\leq{L}\leq{50}$)，為車箱的長度，第二列為整數 1 ~ L 的一種排列組合，表示車箱的起始位置，最後車箱要依照編號 1 到 L 的順序依序排好。

Output Specification

每一列請輸出 Optimal train swapping takes S swaps.，$S$ 為一整數，表示最少需要做幾次車箱置換的步驟。

Example Input

3
3
1 3 2
4
4 3 2 1
2
2 1

Example Output

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

如果一串包含字母或數字的文字由前面讀過來與由後面讀過來都相同的話，則稱為“迴文(a regular palindrome)”，例如 ABCDEDCBA 即是迴文 (a regular palindrome)，因為該字串由左邊開始讀與由右邊開始讀是一樣的。

“鏡像字串 (a mirrored string)” 是一種字串，其字串的每一個字元經過反轉 (reverse) 之後 (假若每一字元有其對應的反轉字元)，倒著讀與原字串相同。例如 3AIAE 即是一個鏡像文字，因為 A 與 I 為自身的反字元 (reverse)，而 3 與 E 互為反字元。

一個 “鏡像迴文字串 (mirrored palindrome)” 是一種字串同時符合迴文字串與鏡像字串的限制，例如 ATOYOTA 即是一個鏡像迴文字串，因為該字串由後面讀過來會與由前面讀過來一樣，且每一個字元經過反轉 (reverse) 之後，其由後面讀過來的結果與原字串相同，畢竟，A、T、O、Y 都是自身的反字元 (reverse)。

所有有效的字元及其對應的反字元如下表所示。

注意：0 (數字零) 與 O (字母 O) 被視為相同的字元，所以只有字母 O 才是有效字元。

Input

輸入資料有多列字串，每一列字串長度介於 1 ~ 20 之間，且必定都是有效字元 (如上表)，絕不會有非有效字元出現。你的程式必須讀到檔案結尾後中止。

Output

針對每一筆輸入字串，你必須先印出該字串後，再接著印出下列字串中的其中一個。

注意：字元 - (dash) 與空白字元是必須的，如上表與下列輸出範例所示。

另外，每一列輸出之後你必須另外再印出一列空行。

Sample Input

NOTAPALINDROME
ISAPALINILAPASI
2A3MEAS
ATOYOTA

Sample Output

NOTAPALINDROME -- is not a palindrome.

ISAPALINILAPASI -- is a regular palindrome.

2A3MEAS -- is a mirrored string.

ATOYOTA -- is a mirrored palindrome.
　

社會研究組識決定採用一組簡單的參數，用來模擬我國政黨運作的行為，其中一個參數為正整數 h (稱為 “罷會參數 (hartal parameter)”) 用來表示同一個政黨連續兩次罷會的間隔時間，雖然這個參數太過簡略了，但還是可以用來預測政黨罷會所帶來的負面影響。接下來的例子會有清楚的說明：

考慮有三個政黨的情況，假設 $h_1 = 3, h_2 = 4, h_3 = 8$，其中 $h_i$ 為政黨 i (i=1, 2, 3) 的 “罷會參數”，接下來我們摸擬這三個政黨在 N = 14 天內的罷會行為，模擬的情況總是設定第一天為星期日，並且每週的例假日 (星期五與星期六) 不會有罷會的情況。

上述的模擬結果顯示 14 天內將罷會 5 天 (第 3, 4, 8, 9, 12 日)，而第 6 天沒有罷會是因為該天是例假日星期五，因此可看出兩週的議程已去掉了 5 天。

本問題會給定各個黨政的 “罷會參數” 與總議程的天數 N，你的任務是算出在 N 天內共有多少個工作天因為各政黨的罷會而導致議程延宕。

Input

輸入的第一列為一個用來表示有幾組測試資料的整數 T。

每組測試資料的第一列為整數 N ($7 \leq N \leq 3650$) ，用來表示所模擬議程的天數。下一列為另一個整數 P ($1 \leq P \leq 100$) 表示共有 P 個政黨，接下來的 P 列分別為各政黨的 “罷會參數” (絕不會為 7 的倍數)。

Output

輸出的每一列表示每一組測試資料所模擬出來的罷會天數 (損失多少個工作天)。

Sample Input

2
14
3
3
4
8
100
4
12
15
25
40

Sample Output

5
15

#include <stdio.h>

main()
{
  int i;
  char *suffix[]= { "st", "nd", "rd" };
  char *item[]= { "Unix" , "cat", "sed", "awk", "grep", "ed", "vi"};

  printf("In the beginning, there was nothing.\n");
  for (i= 0; i < 7; i++)
    printf("And on the %d%s day, God created %s. And it was good.\n",
           i + 1, (i < 3) ? suffix[i] : "th", item[i]);
}

神創造了好用的 Unix 工具之後，祂發現 vi 會使人禁不起誘惑而墮落，因為 vi 功能強大，讓人不願意使用 make, dbx, RCS 等完善的工具，反而用了命令列來編譯、printf()來除錯、磁帶備份來當版本控管的手段。

所以上帝下了命令：因為工程師們褻瀆了我所創造的 vi，所以我決定創造 emacs，這是一個功能強大到無法言喻的文字編輯器，至此，工程師們只要用過一次 vi，就必須為此飽受磨難，注意！磨難必定是痛苦的，一路上將會荊棘遍佈哀鴻遍野，工程師必須讀取很多列文字，並告訴我每一列中出現頻率最高的字母為何，及它總出現幾次。

我命令你們遵守我訂下的鐵則：“不要讓你的朋友使用 vi”

Input and Output

輸出的每一列要包含一列輸入中出現頻率最高的所有字母，並顯示出現多少次。

輸出的字母必須按照字母順序來排序，並且所有大寫字母必須擺在小寫字母之前。

Sample Input

When riding your bicycle backwards down a one-way street, if the
wheel falls of a canoe, how many ball bearings does it take to fill
up a water buffalo?
Hello Howard.

Sample Output

e 6
al 7
a 3
Hlo 2

當一數值以十進位表示時，第 k 位數表示 $10^k$ (十進制由右至左編碼，最低有效位數為第 0 位)。例如：

當一數值以二進制表示時，第 k 位數表示 $2^k$。例如：

當一數值以 “斜偏二進制 (Skew Binary)” 表示時，第 k 位數表示 $2^{k+1} - 1$。除了最低非零的位數可能等於2之外，所有數值皆為 0 或 1。例如：

前十個斜偏二進制 (skew binary) 的數值為 0, 1, 2, 10, 11, 12, 20, 100, 101, 102。(skew binary 在某些領域特別有用，因為它使一數值加上 1 之後，最多只進位一次，但這方面的議題與本題目無關)

Input

輸入檔案有多列，每一列為一整數 n。假如 n=0 代表輸入結束，否則 n 為以斜偏二進制 (skew binary) 表示的非負整數。

Output

對每一個輸入值，輸出它的十進制表示式。n 的十進位值最大可能到 $2^{31} - 1 = 2147483647$。

Sample Input

10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0

Sample Output

44
2147483646
3
2147483647
4
7
1041110737