Сьогодні Степан експериментує із прямокутною таблицею ~A~, яка має ~N~ рядків та ~M~ стовпців та містить цілі числа. Степан хоче знайти суму елементів таблиці, діючи за наступним алгоритмом:

• починаючи з будь якої клітинки першого рядка, переходити на будь який елемент наступного рядка і так робити, поки не досягнемо рядка ~N~. Знаходимо суму вибраних елементів.

Допоможіть Степану вибрати елементи таблиці таким чином, щоб сума була максимально можливою.

Обмеження

• ~1 \le N,M \le 200~
• ~-10^6 \le A_{i,j} \le 10^6~

Input

Перший рядок вхідного потоку містить цілі числа ~N, M~ - та розміри таблиці.

Наступні ~N~ рядків містять по ~M~ цілих чисел ~A_{i,j}~.

Output

Вивести максимальну суму вибраних за алгоритмом Степана елементів.

Sample Input 1

4 3
1 15 2
10 7 5
9 2 10
10 9 -1

Sample Output 1

45

Notes

Вибираємо такі елементи: (1,2) - (2,1) - (3,3) - (4,1).

Степан має масив ~A~, що містить ~N~ цілих чисел. Сьогодні він пропонує вам розв'язати таке завдання.

Нехай ~M~ є найменшим елементом цього масиву. Над елементами масиву дозволяється виконувати таку операцію:

• вибрати довільний елемент ~A_i~ та довільне ціле число ~X~ і виконати присвоєння ~A_i=X~.

Яку мінімальну кількість операцій треба виконати, щоб ~M~ став максимальним елементом оновленого масиву?

Обмеження

• ~1 \le T \le 100~

• ~1 \le N \le 100~

• ~1 \le A_i \le 100~

Input

Перший рядок містить ціле число ~T~ - кількість тестів.

Перший рядок тесту містить ціле число ~N~.

Другий рядок тесту містить ~N~ цілих чисел ~A_i~.

Output

Для кожного тесту виведіть у новому рядку мінімальну кількість операцій, необхідних для того, щоб ~M~ стало максимальним значенням у масиві ~A~.

Sample Input 1

3
2
1 2
4
2 2 3 4
1
1

Sample Output 1

1
2
0

Notes

У першому тесті ~M=1~. Виконаємо таку операцію: виберемо ~A_2~ і ~X=1~. Тоді оновлений масив буде таким: [1,1]. Тепер ~M~ є максимальним елементом оновленого масиву.

Для кодування двійкового рядка парної довжини в послідовність A, T, C та G ми виконуємо ітерацію зліва направо та замінюємо символи наступним чином:

• 00 замінюється на A
• 01 замінюється на T
• 10 замінюється на C
• 11 замінюється на G

Дано двійковий рядок ~S~ довжиною ~N~ ( ~N~ парне). Знайдіть утворену закодовану послідовність.

Обмеження

• ~1 \le T \le 10^2~
• ~2 \le N \le 10^3~
• ~N~ парне.
• ~S~ містить лише 0 та 1.

Input

Перший рядок містить ціле число ~T~ - кількість тестів. Кожен тест містить два рядки вхідних даних.

Перший рядок тесту містить одне ціле число ~N~ - довжину послідовності.

Другий рядок тесту містить двійкову послідовність ~S~.

Output

Для кожного тесту в окремому рядку вивести закодовану послідовність.

Sample Input 1

4
2
00
4
0011
6
101010
4
1001

Sample Output 1

A
AG
CCC
CT

Степан розглядає таблицю з ~H~ рядками та ~W~ стовпцями. Нехай (~i,j~) позначає клітинку в ~i~-му рядку (~1 \le i \le H~) зверху та ~j~-му стовпці (~1 \le j \le W~) зліва.

Кожна клітинка забарвлена одним з кольорів: білим або чорним. Білі клітинки у таблиці позначені '.', а чорні - '#'.

Степан хоче знати, чи його таблиця задовольняє наступну умову:

• для кожної чорної клітинки кількість горизонтально або вертикально суміжних клітинок, забарвлених у чорний колір, дорівнює 2 або 4.

Обмеження

• ~1 \le H,W \le 1000~

Input

Перший рядок містить цілі числа ~H,W~ - кількість рядків та стовпців у таблиці відповідно.

Наступні ~H~ рядків містять по ~W~ символів '.' або '#'.

Output

Вивести 'Yes', якщо таблиця задовольняє умову Степана, або 'No' в іншому випадку.

Sample Input 1

1 2
##

Sample Output 1

No

Sample Input 2

4 3
...
...
...
...

Sample Output 2

Yes

Sample Input 3

2 2
##
##

Sample Output 3

Yes

У Степана нове хобі - він уже тиждень грається із різними послідовностями чисел. Сьогодні у нього чекає вирішення цікава задача. Степан хоче порахувати кількість різних послідовностей, які можна отримати із даної послідовності цілих чисел ~A~ довжиною ~N~, виконавши один раз таку операцію:

• Обрати два числа ~(L,R)~ такі, що ~1 \le L \le R \le N~. Замінити всі елементи підпослідовності ~A_L,A_{L+1},...,A_R~ на ~A_L~.

Скільки різних послідовностей він зможе отримати?

Обмеження

• ~1 \le N \le 10^6~
• ~1 \le A_i \le N~

Input

Перший рядок вхідного потоку містить ціле число ~N~ - довжину послідовності ~A~.

Наступний рядок містить ~N~ цілих чисел ~A_i~.

Output

У вихідний потік вивести одне число - кількість різних послідовностей.

Sample Input 1

4
1 1 2 3

Sample Output 1

4

Notes

Можливі такі різні послідовності:

- (1,1,1,1)

- (1,1,1,3)

- (1,1,2,2)

- (1,1,2,3)