The BBB (short for Byteotian Bit Bank) owns the largest net of cash dispensers in Byteotia. The clients of the BBB can draw their money from the cash dispensers on the basis of a cash card and a 4-digit PIN code. Lately, in order to increase their clients' security, the BBB has had a camera installed by each cash dispenser. The cameras transmit the recorded image to the BBB using radio signals. Unfortunately, the signals are being intercepted by a gang of computer thieves. The thieves attempt to discover the 4-digit PIN codes of the BBB clients, whose cash cards they subsequently steal. Being aware of this fact, the BBB clients try to perform redundant movements over the keyboard while entering the PIN. The camera is not able to pick out the keystrokes, it only records the finger movements. Consequently, it is usually not possible to determine the PIN unambiguously. For instance, the client moving his finger over the key 1 and then over the key 5 could have entered the following PIN codes: 1111, 1115, 1155, 1555, 5555. Desperate thieves glean the camera recordings, counting on being able to determine the PIN of a client or at least limiting the number of possible codes on the basis of multiple recordings of his transactions. Having accumulated sequences entered by a particular wealthy client of the BBB, they made you an "unnegotiable proposition".

Write a programme which:

• reads from the standard input a description of the recorded sequences of finger movements, which the client has performed whilst entering his PIN,
• determines the number of distinct PIN codes, which the client can have (i.e. the number of those 4-digit PIN codes, which could have been entered by performing the given finger movement sequences),
• writes the outcome to the standard output.

Input

The first line of the standard input contains a single integer $n$ denoting the number of recorded scenes depicting the action of entering the PIN by the client, $1 ≤ n ≤ 1,000$. In the following $n$ lines there are descriptions of these scenes, a single one per line. The description of each scene consists of two positive integers separated by a single space. The first of those numbers, $t$, denotes the length of the sequence of movements, $1 ≤ t ≤ 10,000$. The other is a $t$-digit number, whose consecutive digits denote consecutive keys, over which the client has moved his finger. The total length of all sequences does not exceed $1\,000\,000$.

Output

The first and only line of the output should contain a single positive integer - the number of possible PIN codes of the client.

Example

Input

2
3 123
3 234

Output

5