题目内容

一口探井把传感器接成二叉树：每个探头最多向下再接左、右两个探头。巡检员拿到的是这棵树的层序记录，写成字符串 $t$。记录被一对花括号包住，探头编号用逗号隔开，没有挂探头的位置记成 #；末尾连续的空位会省略。空井（一棵空树）写成 {}。

最大深度定义为：从井口根探头走到最远那只叶子探头，路径上经过的探头个数。请根据记录求出最大深度；空井的深度为 0。

约束：

• 探头个数 $m$ 满足 0 $\le$ $m$ $\le$ 100000
• 每个探头编号 $v$ 满足 1 $\le$ $v$ $\le$ 1000000000

输入描述

一行一个字符串 $t$，表示二叉树的层序记录。格式为花括号包裹、逗号分隔，# 表示空位，末尾空位已省略；空树为 {}。

输出描述

输出一个整数，表示最大深度。

样例1

输入

{5,#,8,6}

输出

3

说明

根探头 5 没有左孩子，右孩子是 8，8 的左孩子是 6。最长路径为 $5 \rightarrow 8 \rightarrow 6$，经过 3 个探头。

样例2

输入

{9}

输出

1

说明

只有井口一只探头，深度为 1。

样例3

输入

{}

输出

0

说明

空井没有任何探头，深度为 0。