One-slip search: hints, no solution

A shop search tolerates one slip. A catalogue name matches a query if the query can be turned into that name with at most one edit, where an edit is inserting one letter, deleting one letter or changing one letter into another. An exact match needs no edits and also counts.

For each query, return how many catalogue names match it. Names are distinct lowercase words; queries are lowercase words too, and a query may itself be a catalogue name. Return the counts in query order. Count each name once, even when several different single edits of the query would produce it.

Examples

Input

names = ["cat", "cart", "car", "cut", "at", "bat"], queries = ["cat", "dog", "ca"]

Output

[6, 0, 2]

Note

For cat every listed name is one edit away, including cat itself; for dog none is; for ca only cat and car qualify.

Input

names = ["aa"], queries = ["a", "aaa"]

Output

[1, 1]

Note

The name aa is one inserted letter from a (at either end) and one deleted letter from aaa (either one); it is counted once each time.

Input

names = ["a"], queries = ["b", "a", "ab", "abc"]

Output

[1, 1, 1, 0]

Note

The name a is one changed letter from b, equal to a, one deleted letter from ab, and two edits from abc.

Constraints

• 1 <= names.length <= 20000 and each name has 1 to 12 lowercase letters
• 1 <= queries.length <= 4000 and each query has 1 to 12 lowercase letters
• Names are distinct

Hint 1: a nudge

Which pairs of words are close enough to match? Try the query ca against cat, car, cut and at, and work out which single edit explains each match, and whether some pair can be explained in two ways.

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing