题目内容

射电阵值班员要把一夜的观测记录送进检校台。每条记录是一串只含 0 和 1 的脉冲，分别表示两种正交偏振。台站规程规定：只要当前记录里出现相邻且偏振不同的两位（也就是子串 01 或 10），就可以把这两位同时核销，左右剩下的脉冲再拼成一条新记录，继续检校。核销可以做任意多次，也可以一次都不做。

若某条记录能被核销成空串，检校台就把它记为有效观测。值班员需要统计这批记录里有效观测有多少条。

给出 m 条仅由 0 和 1 组成的字符串。允许反复删掉相邻的一对不同字符（01 或 10），删完后左右拼接。一条串若经过若干次（可以为 0 次）操作后变成空串，则称为可核销。请计算有多少条串是可核销的。

约束：

• 1 $\le$ $m$ $\le$ 200000
• 每条字符串长度在 1 到 100000 之间
• 所有字符串长度之和不超过 500000

输入描述

第一行一个整数 $m$（1 $\le$ $m$ $\le$ 200000），表示字符串条数。

随后 $m$ 行，每行一个仅由 0 和 1 组成的字符串，长度在 1 到 100000 之间。

保证所有字符串长度之和不超过 500000。

输出描述

在一行输出一个整数，表示可核销的字符串条数。

样例1

输入

4
00
11
10
000

输出

1

说明

• 00、11、000 里只有一种字符，删不掉相邻异对，不能核销。
• 10 本身就是一对 10，删一次后变空串，可以核销。
• 因此答案为 1。

样例2

输入

3
1010
1100
1001

输出

3

说明

三条串里 0 和 1 的个数都是 2。

• 1010 可依次删两对 10/01 变空。
• 1100 先删中间的 10 得到 10，再删一次变空。
• 1001 先删中间的 00 不行，但可删前两个 10 得到 01，再删变空。
• 三条都可核销，答案为 3。

样例3

输入

1
111000

输出

1

说明

111000 中 0、1 各 3 个。先删交界处的 10，再继续删相邻异对，可以一直删到空串，故答案为 1。