giaosu vừa mua một bộ trò chơi gồm nhiều chữ cái khác nhau trong bảng chữ cái. Vì mua phải hàng fake nên trong bộ trò chơi số lượng các chữ cái không bằng nhau. giaosu là người rất đẹp trai nên anh ấy đã tìm các chữ cái như:

$$\text{D, E, P, T, R, A, I (Case-sensitive is neglectable)}$$

để ghép thành chữ đẹp trai.

Yêu cầu: Vì quá khó để xác định từ bộ trò chơi trên có thể ghép được bao nhiêu chữ ~\text{DEPTRAI}~ (các chữ cái có thể viết hoa hoặc viết thường) nên anh ấy đã nhờ bạn làm giúp việc đó.

Input Specification

• Dòng thứ nhất nhập vào ~t~ bộ test ~(1 \le t \le 10^4)~.
• Dòng thứ ~t~ nhập vào chuỗi các chữ cái có trong bộ trò chơi của giaosu:
  • Các chữ cái nằm trong bảng chữ cái Latin và có thể viết hoa hoặc viết thường;
  • Độ dài của chuỗi không quá ~128~.

Output Specification

• In ra ~t~ dòng thể hiện số lượng chữ ~\text{DEPTRAI}~ nhiều nhất có thể ghép được.

Sample Input

3
lVUamNzcpQByEmNXqSHatgdtpgAuqbYgGYMFkcjOkmYqfkeICilXbCmmGhRmPb
deptrai
detpaot

Sample Output

1
1
0