Islands in the Data Stream

Interview

Time limit1sMemory limit128 MB

Summary

Count the nested islands, contiguous blocks higher than both neighbors, in each 15-number stream that starts and ends at zero.

Level: Easy3 of 10
Topics: Simulation, Stack
Solved: No attempts yet

Problem

You are given a sequence of integers $a_1, a_2, a_3, \dots, a_n$ . An island is a contiguous block of the sequence in which every element is greater than the element immediately before the block and greater than the element immediately after it. A block with no element before it, or no element after it, is not an island.

An island that lies entirely inside another island still counts as its own island, so each one adds 1 to the total.

You are given a sequence of 15 non-negative integers in which each integer differs from the previous integer by at most 1. Write a program that counts the islands in the sequence.

Input

The first line contains the number of data sets $P$ ( $1 \le P \le 1000$ ). The data sets are independent and are all processed the same way.

Each of the next $P$ lines holds one data set. The line begins with the data set number $K$ , followed by 15 non-negative integers separated by single spaces. The first and the last of those 15 integers are 0. Each integer differs from the previous integer by at most 1.

Output

Print one line for each data set. The line consists of the data set number $K$ , a single space, and the number of islands in that sequence.

Examples1

Example 1

Input

4
1 0 0 1 1 2 2 1 1 0 1 2 2 1 1 0
2 0 1 2 3 4 3 2 1 2 3 4 3 2 1 0
3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0

Expected output