Задача B. Сумма равна произведению

Автор:И. Блинов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Учитель математики придумал игру для развития навыков устного счёта. Учитель записывает на доске таблицу A из N × N натуральных чисел. Затем он вызывает к доске двух учеников, и указывает одно из чисел в таблице (Aij). Первый ученик должен выбрать другое число в той же строке, что и указанное учителем (Aiq, q ≠ j), и сложить с указанным числом. Второй ученик должен выбрать другое число в той же столбце, что и указанное учителем (Apj, p ≠ i), и перемножить с указанным числом.

Если результаты вычислений у двух учеников совпали (Aij + Aiq = Aij × Apj), то ученики получают пятёрки. Чтобы игра была честной, учитель указывает только на такие элементы, для которых существует хотя бы одна подходящая пара чисел. Учитель хочет вызвать как можно больше учеников, указывая каждым на ранее не использованный элемент в таблице.

Требуется написать программу, которая определит количество элементов таблицы, для которых существует хотя бы одна подходящая пара чисел.

По втором примере учитель может выбрать число. 2 (2 + 8 = 2 × 5), 4 (4 + 8 = 4 × 3) либо 3 (3 + 9 = 3 × 4). Если вместо 13 поставить число 5, ответ не изменится, хотя для числа 2 появится второй способ выбора подходящей пары чисел.

Формат входного файла

Входной файл содержит целое число N — размер таблицы, за которым далее следует N строк по N чисел Aij.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество элементов Aij, для которых существуют p ≠ i, q ≠ j, такие что Aij + Aiq = Aij × Apj.

Ограничения

1 ≤ N ≤ 500,

1 ≤ Aij ≤ 109

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
Naij
1151 ≤ N ≤ 101 ≤ Aij ≤ 30
2161 ≤ N ≤ 1001 ≤ Aij ≤ 10001
3221 ≤ N ≤ 2001 ≤ Aij ≤ 10002
4471 ≤ N ≤ 5001 ≤ Aij ≤ 1093

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
2 2
2 2
4
2
4
2  8  12 4
5  6  7  1
9  10 11 3
13 14 15 16 
3
3
2
1000 1000
1000 1000
0

0.077s 0.008s 13