Under construction

Still being built. Things may change

LOL

Interview

Time limit1sMemory limit256 MB

Summary
Find the fewest insertions, replacements, and deletions that make each given word contain lol as a contiguous substring.
Level

Easy3 of 10

Topics
Dynamic programming, String
Solved
No attempts yet

Problem

A word made of lowercase English letters is given. You want to edit it so that it contains lol as a contiguous substring.

One operation is one of the following.

  • Insert one lowercase English letter at any position.
  • Replace one existing letter with another lowercase English letter.
  • Delete one existing letter.

For each word, find the minimum number of operations needed.

Input

The first line contains the number of test cases TT (1≤T≤1001 \le T \le 100).

Each of the next TT lines contains one word. A word is made of lowercase English letters only and its length is at most 5050.

Output

For each word, print on its own line the minimum number of operations that make lol a substring, in the order the words are given.

Examples3

  1. Example 1

    Input
    4
fotball
sopp
ingenting
spillolje
    Expected output
    1
2
3
0

  2. Example 2

    Input
    1
lol
    Expected output
    0

  3. Example 3

    Input
    3
l
o
a
    Expected output
    2
2
3