Background

今天我买了个华为手机，美滋滋！！！！

Description

糟糕，刚刚买的华为手机的密码搞忘了怎么办啊，现在可乐加冰需要你们的帮忙，大概由于可乐加冰比较健忘，手机的密码提示写了一排数字，但是滑动图案却不对，可乐加冰心想：“是不是要换个顺序才能打开？” 现在可乐加冰已经知道手机图案锁是只由哪几个位置组成的,手机图案锁的解锁只能通过一笔画解决,他最多需要多少次情况就一定能够破解该图案锁的密码？每个位置必须经过，每个位置只能够被经过一次。 图案锁的组成有9个位置分别为： 1 2 3 4 5 6 7 8 9 如上图所示： 会提示你密码包含1，2，3，4，5，6，7，8，9. 其中的一种画法如上图：5->4->2->6->7->1->9->8->3. 经过可乐加冰多次研究，发现以下规律： 如果你还没有经过5, 然后你连接了1, 再去连接9的话, 则会经过5. 如果你已经经过5, 然后你连接1, 再去连接9的话, 则不会在重新经过5. 同理可得1和3、4和6等也满足如上规律。

Format

Input

给你一个n表示密码个数和一个数组，表示需要的密码；

Output

输出多少次可以解开手机，如果不能解开则输出“加油华为加油china”

Samples

3
1 5 9

4

2
1 9

加油华为加油china

Limitation

1s, 1024KiB for each test case.