You are given an array a of size n. Each element in this array is an integer between 1 and 109.

You can perform several operations to this array. During an operation, you can replace an element in the array with any integer between 1 and 109.

Output the minimum number of operations needed such that the resulting array doesn't contain any local maximums, and the resulting array after the operations.

An element ai is a local maximum if it is strictly larger than both of its neighbors (that is, ai>ai?1 and ai>ai+1). Since a1 and an have only one neighbor each, they will never be a local maximum.

Input

Each test contains multiple test cases. The first line will contain a single integer t (1≤t≤10000) — the number of test cases. Then t test cases follow.

The first line of each test case contains a single integer n (2≤n≤2?105) — the size of the array a.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109), the elements of array.

It is guaranteed that the sum of n over all test cases does not exceed 2?105.

Output

For each test case, first output a line containing a single integer m — minimum number of operations required. Then ouput a line consist of n integers — the resulting array after the operations. Note that this array should differ in exactly m

?elements from the initial array.

If there are multiple answers, print any.

Example

input

5

3

2 1 2

4

1 2 3 1

5

1 2 1 2 1

9

1 2 1 3 2 3 1 2 1

9

2 1 3 1 3 1 3 1 3

output

0

2 1 2

1

1 3 3 1

1

1 2 2 2 1

2

1 2 3 3 2 3 3 2 1

2

2 1 3 3 3 1 1 1 3

Note

In the first example, the array contains no local maximum, so we don't need to perform operations.

In the second example, we can change a2 to 3, then the array don't have local maximums.

中文翻譯：

給定一個大小為 n 的數(shù)組 a。 該數(shù)組中的每個元素都是 1 到 109 之間的整數(shù)。

您可以對此數(shù)組執(zhí)行多項操作。 在操作過程中，您可以將數(shù)組中的元素替換為 1 到 109 之間的任何整數(shù)。

輸出所需的最小操作數(shù)，以使結果數(shù)組不包含任何局部最大值，以及操作后的結果數(shù)組。

如果元素 ai 嚴格大于其兩個鄰居（即 ai>ai?1 且 ai>ai+1），則該元素 ai 是局部最大值。 由于 a1 和 an

? 每個都只有一個鄰居，它們永遠不會是局部最大值。

輸入

每個測試包含多個測試用例。 第一行將包含一個整數(shù) t (1≤t≤10000) — 測試用例的數(shù)量。 然后

? 測試用例如下。

每個測試用例的第一行包含一個整數(shù) n (2≤n≤2?105) — 數(shù)組 a 的大小。

每個測試用例的第二行包含n個整數(shù)a1,a2,…,an? (1≤ai≤109)，數(shù)組的元素。

保證所有測試用例的 n 之和不超過 2?105。

輸出

對于每個測試用例，首先輸出一行包含單個整數(shù) m

? ——所需的最少操作次數(shù)。 然后輸出一行由 n 個整數(shù)組成的行——運算后的結果數(shù)組。 請注意，此數(shù)組與初始數(shù)組應恰好有 m 個元素不同。

如果有多個答案，請打印其中一個。

----------------------------------------------------------------

當我們遇到一個比兩邊數(shù)字都大的位置的時候，我們要把后面的數(shù)字改為最大值，后面的數(shù)字改成后面數(shù)字左右的最大值，當然如果是最后一個，特例判斷即可，剩下就是記錄這種情況的次數(shù)，然后輸出數(shù)組；

下面是代碼：