Билет — это непустая строка из цифр от \(1\) до \(9\).
Счастливый билет — это такой билет, у которого:
- четная длина;
- сумма цифр в первой половине равна сумме цифр во второй половине.
У вас есть \(n\) частей билетов \(s_1, s_2, \dots, s_n\). Сколько пар \((i, j)\) (для \(1 \le i, j \le n\)) существует таких, что \(s_i + s_j\) является счастливым билетом? Обратите внимание, что возможно \(i=j\).
Здесь оператор + обозначает конкатенацию двух строк. Например, если \(s_i\) — это 13, а \(s_j\) — это 37, то \(s_i + s_j\) будет 1337.
Выходные данные
Выведите одно целое число — количество пар \((i, j)\) (для \(1 \le i, j \le n\)), таких что \(s_i + s_j\) является счастливым билетом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
5 93746 59 3746 593 746 5937 46 59374 6
|
20
|
|
2
|
5
2 22 222 2222 22222
|
13
|
|
3
|
3
1 1 1
|
9
|