Suffix Pairs

Given an array of strings words, find the number of pairs where either the strings are equal or one string ends with another. In other words, find the number of such pairs (i, j) (0 ≤ i < j < words.length) that words[i] is a suffix of words[j].

Constraints

• 1 ≤ words.length ≤ 10⁵
• 1 ≤ words[i].length ≤ 10

Example 1

Input:

words = ["hack", "hackhour", "jammon", "backgammon", "comeback", "come", "door"]

Output:

3

Explanation: The relevant pairs are:

• words[0] = "hack" and words[1] = "comeback"
• words[1] = "hackhour" and words[6] = "door"
• words[2] = "jammon" and words[3] = "backgammon"

Example 2

Input:

words = ["cha", "a", "a", "b", "ba", "ca"]

Output:

8

Explanation: The relevant pairs are:

• words[0] = "cha" and words[1] = "a"
• words[0] = "cha" and words[2] = "a"
• words[0] = "cha" and words[4] = "ba"
• words[1] = "a" and words[2] = "a"
• words[1] = "a" and words[4] = "ba"
• words[1] = "a" and words[5] = "ca"
• words[2] = "a" and words[4] = "ba"
• words[2] = "a" and words[5] = "ca"