Sina wrote some text and now she wants to know how many circles are in the text. What is a circle? If you think of the paper as the plane and a letter as a curve on the plane, then each letter divides the plane into regions. For example letters "A", "D", "O", "P", "R" divide the plane into two regions so we say these letters each have one circle. Similarly, letter "B" has two circles and "C", "E", "F", "K" have no circles. Help Sina to determine how many circles are in the text.

Input The first line contains a single integer T <= 40, the number of test cases. T test cases follow. The only line of each test case contains a non-empty text composed only of uppercase letters of English alphabet. The length of the text is less then 100. There are no any spaces in the input.

Output For each test case, output a single line containing the number of circles in the corresponding text.

Example

Input:

2
HACKEREARTH
JECCODEBASE

Output:

4
5