URI Online Judge | 3006

Copacabana Tour

By Paulo E. D. Pinto, Universidade do Estado do Rio de Janeiro BR Brazil

Timelimit: 3

There are many  restaurants, cafes and drugstores on the Avenue Copabacana. Floriano wants to walk a stretch of this avenue to eat a bean stew, have a coffee and, cautiously, go to a pharmacy to buy a preventive medicine. He wants to take a taxi to the restaurant and then walk to a coffee shop and pharmacy, take a cab back, but he doesn't want to walk much.

Given the locations of pharmacies, cafes, and restaurants on this avenue, you should choose which items you should use to walk as little as possible. Note which one first has a restaurant and then, in any order, a cafe and a pharmacy.

Input

The input consists of a series of tests. The first line contains a single integer indicating the number n (1 ≤ n ≤ 20) of test cases. Following are n lines each containing a test case. Each test case is a string, less than or equal to 1000000, containing the positions of restaurants, pharmacies, and cafes, as follows:

   . A 'R' character represents the position of a restaurant.

   . A 'F' character represents the position of a pharmacy.

   . A  'C' represents the position of a coffee.

 . A  '.' represents the position of an uninteresting establishment.

You can assume that there will be at least one restaurant, a cafe and a pharmacy.

Output

For each test case print, on one line, the shortest distance Floriano should walk.

Input Sample Output Sample

3

C...R...F

CR.CR.CCF

C.C.R..RF

12

4

7