Description

The BBB (short for Byteotian Bit Bank) owns the largest network of cash dispensers in Byteotia. The clients of the BBB can withdraw money from cash dispensers using a cash card and a 4-digit PIN code. Recently, to increase client security, the BBB has installed a camera by each cash dispenser. The cameras transmit the recorded image to the BBB using radio signals. Unfortunately, these signals are being intercepted by a gang of computer thieves. The thieves try to discover the 4-digit PIN codes of BBB clients, whose cash cards they subsequently steal. Aware of this, BBB clients try to make redundant movements over the keyboard while entering the PIN. The camera cannot pick out the actual keystrokes; it only records the finger movements. Consequently, it is usually impossible to determine the PIN unambiguously. For instance, a client moving a finger over key 1 and then over key 5 could have entered the following PIN codes: 1111, 1115, 1155, 1555, 5555. Desperate thieves analyze the camera recordings, hoping to determine the client’s PIN or at least limit the number of possible codes based on multiple recordings of his transactions. Having accumulated sequences entered by a particular wealthy client of the BBB, they made you an "unnegotiable proposition".

Task: Write a program that:

• reads from standard input a description of the recorded sequences of finger movements performed while entering the PIN,
• determines the number of distinct 4-digit PIN codes the client can have (i.e., the number of 4-digit PIN codes that could have been entered while performing each of the given finger movement sequences),
• writes the result to standard output.

Input Format

The first line contains a single integer $n$ denoting the number of recorded scenes of entering the PIN by the client, $1\le n\le 1\ 000$. Each of the following $n$ lines describes one scene and consists of two positive integers separated by a single space. The first number, $t$, denotes the length of the movement sequence, $1\le t\le 10\ 000$. The second is a $t$-digit number whose consecutive digits denote consecutive keys over which the client moved a finger. The total length of all sequences does not exceed $1\ 000\ 000$.

Output Format

Print a single positive integer: the number of possible PIN codes of the client.

2
3 123
3 234

5

Hint

Translated by ChatGPT 5