Count Prefix and Suffix Pairs

You are given an array of strings words. A string words[i] is a prefix-suffix pair of words[j] if words[i] is both a prefix and a suffix of words[j].

Return the number of pairs (i, j) where 0 <= i < j < words.length such that words[i] is both a prefix and a suffix of words[j].

Examples

Example 1:

Input: words = ["a","aba","ababa","aa"]

Output: 4

Explanation: The valid pairs are:

• (0, 1): "a" is a prefix and suffix of "aba"
• (0, 2): "a" is a prefix and suffix of "ababa"
• (0, 3): "a" is a prefix and suffix of "aa"
• (1, 2): "aba" is a prefix and suffix of "ababa"

Example 2:

Input: words = ["pa","papa","ma","mama"]

Output: 2

Explanation: The valid pairs are:

• (0, 1): "pa" is a prefix and suffix of "papa"
• (2, 3): "ma" is a prefix and suffix of "mama"

Example 3:

Input: words = ["abab","ab"]

Output: 0

Explanation: "ab" is a prefix of "abab" but not a suffix, and since i < j, the pair (1, 0) is not valid.

Constraints

• 1 <= words.length <= 50
• 1 <= words[i].length <= 10
• words[i] consists of only lowercase English letters