github.com/captn3m0/codechef.git

---
category_name: easy
problem_code: BROKPHON
problem_name: 'Broken Telephone'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYPY
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM chicken'
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '1'
source_sizelimit: '50000'
problem_author: m0stik
problem_tester: xcwgf666
date_added: 25-01-2015
tags:
    - april15
    - cakewalk
    - loops
    - m0stik
editorial_url: 'http://discuss.codechef.com/problems/BROKPHON'
time:
    view_start_date: 1428917400
    submit_start_date: 1428917400
    visible_start_date: 1428917400
    end_date: 1735669800
    current: 1493558111
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/APRIL15/mandarin/BROKPHON.pdf) and [Russian](http://www.codechef.com/download/translated/APRIL15/russian/BROKPHON.pdf).

Chef is judging a game called "Broken telephone". There are total **N** players taking part in the game. They are all sitting in a line. In the start of the game, first player is given a secret message written on a sheet of paper. Then they keep sending the message by whispering it to the player sitting immediate right to one and so on until it reaches the last person.

Finally, the message received by the last player is compared with the message said by first player. If these messages aren't equal, there is someone who has misheard the message or whispered it wrongly to the next player. If messages is equal, then the players win and receive a tasty chocolate.

Note that first player receives the message on a sheet of paper, thus he cannot mishear it.

As Chef wants to be sure that every player has fulfilled his/ her role in the game, so he asks everyone to state their received messages after the end of the game. You are given an array **A** of **N** integers denoting messages received by each person.

Please help Chef to find the number of players that could mishear the message or whisper it wrongly.

### Input

- The first line of the input contains an integer **T** denoting the number of test cases.
- The first line of each test case contains a single integer **N** denoting the number of players
- The second line contains **N** space-separated integers **A1**, **A2**, ..., **AN** denoting the messages of players.

### Output

- For each test case, output a single line containing an integer corresponding to the number of players that could mishear the message or whisper it wrongly.

### Constraints and Subtasks

- **1** ≤ **T** ≤ **5**
- **1** ≤ **Ai** ≤ **109**

**Subtask 1: 40 points**

- **2** ≤ **N** ≤ **103**

**Subtask 2: 60 points**

- **2** ≤ **N** ≤ **105**

### Example

<pre><b>Input:</b>
3
7
1 1 1 3 3 3 2
5
1 3 1 1 1
4
5 5 5 5

<b>Output:</b>
4
3
0
</pre>### Explanation

- **Example 1**: The **3-rd**, **4-th**, **6-th** and **7-th** player could mishear the message or whisper it wrongly.
- **Example 2**: First **3** players could mishear the message or whisper it wrongly.