三年前，你曾帮助小彼得将他的玩具积木堆成一座塔。从那时起，他扩充了他的积木收藏，现在包含了以下几种基础形状： circle a —— 半径为 $a$ 的圆； square a —— 边长为 $a$ 的正方形； * triangle a —— 边长为 $a$ 的等边三角形。

这里，$a$ 可以是任何正整数。每块积木的顶面形状与其底面形状相同，因此这些积木分别是长方体、圆柱体和三棱柱。彼得拥有每种形状和尺寸的无限供应积木。

图 A.1：游戏进行中。

彼得和他的朋友艾米正在玩一个双人游戏，积木需要堆叠在一起。最初，一些积木已经放置在地板上。在每一轮中，当前玩家必须从无限供应的积木中取出一块，并将其放置在现有的某个积木堆的顶部。积木在放置前可以绕其垂直轴旋转。新积木的轮廓必须严格位于旧积木的轮廓之内；轮廓不允许接触。第一个无法进行移动的玩家输掉游戏。

给定初始配置，确定第一个玩家获胜的移动方案数。

输入格式

输入包含： 一行一个整数 $n$ ($1 \le n \le 1000$)，表示初始积木堆的数量。 $n$ 行，每行包含一个字符串 $s$（$s$ 为 “circle”、“square” 或 “triangle” 之一）和一个整数 $a$ ($1 \le a \le 10^9$)，给出如上所述的初始积木堆顶部的积木。

输出格式

输出第一个玩家获胜的移动方案数。

样例

样例输入 1

2
circle 2
triangle 2

样例输出 1

2

样例输入 2

2
circle 1
circle 2

样例输出 2

3

样例输入 3

5
circle 123
triangle 456
square 789
square 789
triangle 555

样例输出 3

7

样例输入 4

3
circle 299303201
square 79724391
triangle 437068198

样例输出 4

3

样例输入 5

3
square 539715887
circle 518408351
triangle 348712924

样例输出 5

0

说明

图 A.2：样例输入 2 的说明，展示了彼得先手并以最优策略获胜时所有可能的最终配置。蓝色积木为初始配置。彼得需要将 `circle 1`、`square 2` 或 `triangle 3` 中的一个放在 `circle 2` 上才能获胜。这些选项中的每一个都对应图中的一行。彼得放置的积木为红色，艾米放置的积木为黄色。由于最后两块积木总是 `triangle 1` 类型，它们以灰色显示。例如，如果彼得首先放置 `circle 1`（如第一行所示），那么彼得可以通过镜像艾米的后续移动来获胜。