PLU Count

Interview

Time limit1sMemory limit128 MB

Summary
For each text string, find the largest k such that PLU repeated k times is a subsequence, ignoring case.
Level

Easy3 of 10

Topics
Greedy, String, Implementation
Solved
No attempts yet

Problem

Given a text string, find the maximum number of non-interleaved occurrences of PLU in it. In each occurrence the letters P, L, U must appear in that order; capitalization does not matter and the letters need not be consecutive. However, one occurrence must be completed (P, then L, then U) before the next one may begin. Equivalently, find the largest kk such that the string PLU repeated kk times (PLUPLU…) is a subsequence of the text. For example, the string pppxLLLxuuu has just one non-interleaved occurrence of PLU.

Input

The first line is a positive integer nn, the number of text strings that follow. Each of the next nn lines contains one text string. Each string is at most 80 characters long, and there are no blank lines.

Output

For each text string, print on its own line the maximum number of non-interleaved occurrences of PLU, as described above.

Examples1

  1. Example 1

    Input
    3
Please find the number of parts listed under automotive.
The building was constructed for the public.
pppxLLLxuuu
    Expected output
    2
0
1