1221. Count Square Submatrices with All Ones

Given a binary matrix of 0s and 1s, count all square submatrices (of any size) that contain only 1s. The input is JSON {matrix}.

Input: JSON {matrix}.

Output: Integer — the number of all-ones square submatrices.

Examples

Example 1

Input: {"matrix":[[0,1,1,1],[1,1,1,1],[0,1,1,1]]}
Output: 15
Explanation: Ten 1x1, four 2x2, one 3x3.

Example 2

Input: {"matrix":[[1,0,1],[1,1,0],[1,1,0]]}
Output: 7
Explanation: Six 1x1 and one 2x2.

Example 3

Input: {"matrix":[[1]]}
Output: 1
Explanation: Single cell.