Given a string `s`. In one step you can insert any character at any index of the string.

Return _the minimum number of steps_ to make `s` palindrome.

A **Palindrome String** is one that reads the same backward as well as forward.

**Example 1:**

**Input:** s =  "zzazz "
**Output:** 0
**Explanation:** The string  "zzazz " is already palindrome we do not need any insertions.

**Example 2:**

**Input:** s =  "mbadm "
**Output:** 2
**Explanation:** String can be  "mbdadbm " or  "mdbabdm ".

**Example 3:**

**Input:** s =  "leetcode "
**Output:** 5
**Explanation:** Inserting 5 characters the string becomes  "leetcodocteel ".

**Constraints:**

*   `1 <= s.length <= 500`
*   `s` consists of lowercase English letters.


def extract_artifacts(n, artifacts, dig):
    artifact_cells = {}
    artifact_count = {}

    for i, (r1, c1, r2, c2) in enumerate(artifacts):
        for r in range(r1, r2 + 1):
            for c in range(c1, c2 + 1):
                cell = r * n + c
                if cell not in artifact_cells:
                    artifact_cells[cell] = set()
                artifact_cells[cell].add(i)
                artifact_count[i] = artifact_count.get(i, 0) + 1

    ans = 0
    for r, c in dig:
        cell = r * n + c
        if cell in artifact_cells:
            for artifact_id in artifact_cells[cell]:
                artifact_count[artifact_id] -= 1
                if artifact_count[artifact_id] == 0:
                    ans += 1
            del artifact_cells[cell]

    return ans
