Description

众所周知，天朝泱泱五千年的文化积淀下，人们在数字上尤为挑剔。很多人认为，不吉利的数字会导致流年困顿。「阿弥陀佛，作为社会主义接班人，我们应该相信科学，远离迷信!」

在天朝，不同的人读手机号码有不同的方式（见右图）。人们选择手机号码时，为了照顾“不吉利数字恐惧症”患者，总会希望任何人报自己的电话号码时都不会连续说出来不吉利数字。

例如，很多天朝子民认为5914是一串很不吉利的号码，因此尾号为5914的手机号码理所当然地被众人所避忌。而号码188-8859-1488却不是一个不吉利号码，因为无论使用右图中的哪一种方式去读，5914均会被拆分开来。

现在，我们想知道的是，在天朝，有多少电话号码能被人们所接受。

* 常识：在中国，民用手机号段均以1开头。

Input

第一行输入一个正整数N，表示有N个不吉利的数字串。

接下来N行，每行一个5位以内的数字串，表示一个不吉利的号码。

Output

一个正整数，表示并非不吉利的号码总数。

Sample I/O

Hint

对于20% 的数据，N ≤ 2；

对于100% 的数据，N ≤ 100；

题解

出题人Eolv：

对右图所示四种读电话号码的方式进行总结，可得到信息：

符合题意的电话号码中第1~4位、第4~7位、第5~8位、第7~11位均不包含不吉利数字串。

令f[i,x]表示对于前i位号码，以数字串x结尾的方案数。显然，只需要依次求出f[4,0…9]、f[7,000…999]、f[8,00…99]、f[11,00000…99999]即可统计出答案。由于不吉利数字串的总数较少，转移时直接枚举所有的情况即可。也可以建立AC自动机对这一过程进行优化。