Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

dp

hashing

implementation

math

*1400

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Torn Lucky Ticket

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputA ticket is a non-empty string of digits from $$$1$$$ to $$$9$$$.

A lucky ticket is such a ticket that:

- it has an even length;
- the sum of digits in the first half is equal to the sum of digits in the second half.

You are given $$$n$$$ ticket pieces $$$s_1, s_2, \dots, s_n$$$. How many pairs $$$(i, j)$$$ (for $$$1 \le i, j \le n$$$) are there such that $$$s_i + s_j$$$ is a lucky ticket? Note that it's possible that $$$i=j$$$.

Here, the + operator denotes the concatenation of the two strings. For example, if $$$s_i$$$ is 13, and $$$s_j$$$ is 37, then $$$s_i + s_j$$$ is 1337.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of ticket pieces.

The second line contains $$$n$$$ non-empty strings $$$s_1, s_2, \dots, s_n$$$, each of length at most $$$5$$$ and consisting only of digits from $$$1$$$ to $$$9$$$.

Output

Print a single integer — the number of pairs $$$(i, j)$$$ (for $$$1 \le i, j \le n$$$) such that $$$s_i + s_j$$$ is a lucky ticket.

Examples

Input

105 93746 59 3746 593 746 5937 46 59374 6

Output

20

Input

52 22 222 2222 22222

Output

13

Input

31 1 1

Output

9

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 05:54:21 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|