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

Yêu cầu: Hãy đếm số cách khác nhau để chia ~N~ thành tổng ~3~ số chính phương.

Ví dụ: ~74 = 9 + 16 + 49 = 3^2 + 4^2 + 7^2~

Hai cách chia được gọi là khác nhau nếu các số hạng thành phần tạo nên chúng khác nhau.

Input Specification

• Một dòng duy nhất là số nguyên ~N~.

Output Specification

• Một dòng duy nhất là kết quả.

Limitations

• Subtask 1 [~25\%~]: ~1 \le N \le 10^2~
• Subtask 2 [~25\%~]: ~1 \le N \le 10^3~
• Subtask 3 [~50\%~]: ~1 \le N \le 10^6~

Sample Input

2

Sample Output

1

Sample Explanation

• 0 1 1 và các hoán vị của chúng.

Một dãy phố gồm ~N~ tòa nhà được xây liên tiếp nhau trên một đường thẳng, tòa nhà thứ ~i~ có chiều cao là ~h_i~. Trưởng thành phố muốn nối dây mạng liên thông giữa các tòa nhà bằng nhau nên nhờ bạn giúp đỡ.

Với mỗi cặp tòa nhà ~i, j~, với ~i < j~ và ~h_i = h_j~. Nếu như không có tòa nhà nào chắn giữa ~i~ và ~j~ thì cần nối một đoạn dây có độ dài ~i - j - 1~ giữa hai tòa nhà.

Yêu cầu: Hãy tính tổng độ dài đoạn dây tối thiểu để nối các dây mạng liên thông.

Input Specification

• Dòng đầu tiên gồm một số nguyên dương ~N~ - số lượng tòa nhà.
• Dòng thứ hai gồm ~N~ số nguyên dương ~h_i~ - độ cao của tòa nhà.

Output Specification

• Một dòng duy nhất là kết quả.

Limitations

• Subtask 1 [~30\%~]: ~1 \le N \le 10^3; 1 \le h_i \le 10^2~
• Subtask 2 [~70\%~]: ~1 \le N \le 10^6; 1 \le h_i \le 10^4~

Sample Input

9
1 2 1 1 2 1 1 2 1

Sample Output

4

Sample Explanation

Hình 1. Mô phỏng ví dụ

Điện trở là loại linh kiện phổ biến trong mạng lưới điện, các mạch điện tử. Điện trở (Resistor) là một linh kiện điện tử thụ động gồm ~2~ tiếp điểm kết nối, thường được dùng để hạn chế cường độ dòng điện chảy trong mạch, điều chỉnh mức độ tín hiệu, dùng để chia điện áp, kích hoạt các linh kiện điện tử chủ động như Tranzito (Transistor), tiếp điểm cuối trong đường truyền điện và có trong rất nhiều ứng dụng khác.

Bạn có thể bỏ qua phần nội dung trong spoiler nếu bạn cảm thấy đã có đủ kiến thức để làm bài!

Theo định luật Ohm (theo Sách giáo khoa Vật lý 9, tái bản 2015 // theo Sách giáo khoa Vật lý 11 bản Nâng cao cho ban Khoa học tự nhiên, tái bản 2015):

Cường độ dòng điện qua dây dẫn tỷ lệ thuận với hiệu điện thế đặt vào hai đầu dây và tỷ lệ nghịch với điện trở của dây. Theo đó, ta thiết lập công thức: $$I = \frac{U}{R} \text{ with } \begin{cases} \text{I is The current passing through the Resistor;} \\ \text{U is Voltage accross the Resistor;} \\ \text{R is Resistance.} \end{cases}$$

Đối với đoạn mạch gồm hai điện trở mắc nối tiếp:

• Cường độ dòng điện có giá trị như nhau tại mọi điểm: ~I = I_1 = I_2 = I_{\dots} = I_n~;
• Hiệu điện thế giữa hai đầu đoạn mạch bằng tổng hai hiệu điện thế giữa hai đầu mỗi điện trở thành phần: ~U = U_1 + U_2 + U_{\dots} + U_n~;
• Điện trở tương đương của đoạn mạch bằng tổng các điện trở thành phần: ~R = R_1 + R_2 + R_{\dots} + R_n~.

Hình 1. Ba điện trở mắc nối tiếp

Đối với đoạn mạch gồm hai điện trở mắc song song:

• Cường độ dòng điện có giá trị bằng tổng cường độ dòng điện chạy qua các mạch rẽ: ~I = I_1 + I_2 + I_{\dots} + I_n~;
• Hiệu điện thế giữa hai đầu đoạn mạch bằng hiệu điện thế giữa hai đầu mỗi đoạn mạch rẽ: ~U = U_1 = U_2 = U_{\dots} = U_n~;
• Nghịch đảo của điện trở tương đương bằng tổng các nghịch đảo của các điện trở thành phần: ~\dfrac{1}{R} = \dfrac{1}{R_1} + \dfrac{1}{R_2} + \dfrac{1}{R_{\dots}} + \dfrac{1}{R_n}~.

Hình 2. Ba điện trở mắc song song

Yêu cầu: Bạn được cheeseytunaa giao cho một mạch điện, tuy vậy suất điện động của nguồn điện chính (coi điện trở suất của nguồn điện là lý tưởng, xấp xỉ ~\approx 0~), hãy làm ra một mạch tiêu hao năng lượng dùng một hoặc nhiều điện trở giống nhau ghép Nối tiếp hoặc Song song nhau, hoặc kết hợp cả hai. Tuy vậy, cheeseytunaa với số tiền có hạn, hãy giúp anh ấy tìm ra phương pháp tối ưu để mua ít điện trở nhất.

Input Specification

• Dòng đầu tiên chứa ~3~ tham số lần lượt là ~U~, ~I~ và ~R_{\text{sub}}~:
  • ~U~ là hiệu điện thế đo được toàn mạch;
  • ~I~ là cường độ dòng điện;
  • ~R_{\text{sub}}~ là giá trị điện trở suất của một điện trở.

Output Specification

• In ra một số nguyên dương là số lượng điện trở ít nhất mà cheeseytunaa cần mua.

Limitations

• Các giá trị của ~U~ và ~I~ được giới hạn với ~1 \le U, I \le 10^9~.
• Subtask 1 [~10\%~]: ~R_{\text{sub}} = 1~.

Các subtasks dưới đây được giới hạn với ~R_{\text{sub}} \in \{6; 9; 69; 420; 123\}~:

• Subtask 2 [~30\%~]: Giá trị của ~U~ và ~I~ làm cho ~R_{\text{tđ}}~ là số nguyên dương.
• Subtask 3 [~20\%~]: Giá trị của ~U~ và ~I~ làm cho ~R_{\text{tđ}}~ là số thập phân với ~2~ chữ số sau phần thập phân.
• Subtask 4 [~20\%~]: Giá trị của ~U~ và ~I~ làm cho ~R_{\text{tđ}}~ là số thập phân vô hạn tuần hoàn.
• Subtask 5 [~20\%~]: Không có điều kiện gì thêm.

Sample Input

3 1 2

Sample Output

3

Sample Explanation

• Điện trở tương đương của toàn mạch theo định luật Ohm: ~R = \dfrac{3}{1} = 3~;
• Ta sẽ mắc các điện trở như sau:

Hình 3. Mô phỏng trực quan / Giải thích cho ví dụ

• Tổng cộng tốn ít nhất ~3~ điện trở.

Một trò chơi có tên là Lights Out, luật chơi như sau:

Một bảng đèn hình chữ nhật gồm:

• ~n~ dòng được đánh số ~1..n~
• ~m~ cột được đánh số ~1..m~

Với mỗi một thao tác trên một đèn ~(x; y)~ bất kì, bạn sẽ thay đổi trạng thái của bòng đèn ~(x; y)~ và các bóng đèn khác có chung cạnh với nó.

Yêu cầu: Nhiệm vụ của bạn trong trò chơi này là tắt hết tất cả đèn. Hãy in ra một bảng gồm 1 nếu bạn thao tác trên bóng đèn đó hoặc 0 nếu ngược lại.

Bạn có thể chơi thử tại đây: https://www.logicgamesonline.com/lightsout

Input Specification

• Gồm hai số nguyên dương ~n, m~ - kích thước của bảng ~(m \le 8, n \le 10^4)~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ kí tự 1 nếu đèn ô đó bật hoặc 0 nếu ngược lại.

Output Specification

• In ra một bảng thể hiện thao tác của bạn, 1 nếu bạn thao tác ô đó và 0 ngược lại

Limitations

Note: Dữ liệu đảm bảo luôn có kết quả!

• Subtask 1 [~30\%~]: ~m = 2~
• Subtask 2 [~15\%~]: ~n \times m \le 22~
• Subtask 3 [~55\%~]: Không có giới hạn gì thêm.

Sample Input

6 5
00100
01110
00100
00100
01110
00100

Sample Output

00000
00100
00000
00000
00100
00000

Đây là một bài tập interactive!

Một trận động đất đã xảy ra tại nhà khiemkrkt, tuy vậy thì con robot hút bụi của anh ấy vẫn còn sống. Con Robot xuất phát tại một điểm nào đó ở trong mê cung hình chữ nhật ~n \times m~ nhưng chúng ta không biết ở tọa độ nào.

Yêu cầu: Vì không muốn tốn tiền nên anh ấy muốn nhờ bạn lập trình con Robot đi mò đường cho đến khi gặp được ô có lối ra.

Interaction

• Robot gửi thông tin của bốn bức tưởng xung quanh bằng một dãy nhị phân phân gồm ~4~ ký tự thể hiện hướng lên-trái-xuống-phải:
  • 1 nếu bạn có thể đi về hướng đó;
  • 0 nếu ở đó có bức tường.
• Sau đó chọn một trong bốn hướng để di chuyển UP, LEFT, DOWN, RIGHT rồi cứ thế tiếp tục.
• Đến cuối lượt tương tác sẽ xảy ra ~2~ trường hợp:
  • Khi gặp lối ra, robot gửi thông tin OK cho bạn, bạn nhận được verdict AC.
  • Nếu bạn đụng tường, robot sẽ bị hỏng và bạn nhận được verdict WA.

Limitations

• ~2 \le n, m \le 100~
• Subtask 1 [~30\%~]: Robot luôn bắt đầu ở vị trí trái trên của bảng và lối ra luôn ở ô phải dưới của bảng.
• Subtask 2 [~70\%~]: Không có giới hạn gì thêm.

Sample Series Of Interactions

Explanation

Hình 1. Mô phỏng trực quan / Giải thích cho ví dụ