Ôn luyện vào chuyên Tin #04

Nhóm đồ án gồm Khôi, Huy, Cường đang cùng nhau tạo ra một app có thể chỉnh sửa gương mặt mang tên FaceApp. Tuy nhiên, họ đang gặp rắc rối với thuật toán nhận diện khuôn mặt.

Trong vấn đền này, một bức ảnh có thể biểu diễn thành \(1\) bảng ô \(m \times n\) bằng các ký tự latin thường (từ \(a\) đến \(z\)). Một ô \(2\) x \(2\) sẽ được tính là một gương mặt nếu từ \(4\) ô này có thể tạo thành chữ \(“face”\).
Bạn hãy giúp Khôi viết một chương trình đếm có bao nhiêu gương mặt trong bức hình. Biết rằng một ô có thể thuộc nhiều gương mặt.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\), \(m\) \((1 \leq n,m \leq 50)\) – lần lượt là chiều cao và chiều rộng của bức ảnh.
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) ký tự latin thường

Output

• Số gương mặt trong bức hình.

Example

4 4
xxxx
xfax
xcex
xxxx 

 1

2 3
fac
cef 

2

1 4
face 

0

Bạn được cho 2 số nguyên dương \(n\), \(k\) .Hãy tìm số thứ \(k\) không chia hết cho \(n\)

Ví dụ: \(n=3\), \(k=7\) Tất cả các số không chia hết cho \(n\) là \(1,2,4,5,7,8,10,11,13,…\) Vậy số thứ \(k\) không chia hết cho \(3\) là số \(10\).

Input

• Dòng đầu tiền : Số nguyên dương \(q\) \((q \leq 1000)\)- số câu hỏi
• \(q\) dòng tiếp theo chứa 2 số nguyên dương \(n\) và \(k\) \((2 \leq n \leq 10^9, 1 \leq k \leq 10^9)\)

Output

• Gồm \(q\) dòng, mỗi dòng chứa số nguyên dương thứ \(k\) không chia hết cho \(n\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n,k \leq 10^5\)
• Subtask \(2\) (\(50\%\) số điểm): \(n,k \leq 10^9\)

Example

6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1 

10
15
1999999999
113
1000000001
1

Khôi rất thích chơi Liên Minh Huyền Thoại, đặc biệt là vị tướng Yasuo. Tuy nhiên anh ấy chơi Yasuo rất tệ nên anh ấy đang tập luyện để chơi vị tướng này một cách thành thạo.

Biết rằng từ tọa độ \((x,y)\) Yasuo có thể lướt thẳng đến một trong các vị trí $(x-1,y), (x+1,y), (x,y-1), (x,y+1) $

hoặc lướt chéo đến một trong các vị trí \((x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)\)

Khôi sẽ tập luyện lướt Yasuo trong \(Q\) trận, trong trận thứ \(i\) mục tiêu của anh ấy là lướt tới điểm \((n,m)\) từ tọa độ \((0,0)\) trong chính xác \(k\) lần lướt. Tuy nhiên vì để được Thông Thạo 7 Yasuo, Khôi sẽ lướt đến điểm \((n,m)\) với số lần lướt chéo là nhiều nhất.

Câu hỏi của bạn là, trong trận thứ \(i\), bạn hãy xác định số lần lướt chéo nhiều nhất của Khôi hoặc nói rằng Khôi không thể lướt từ điểm \((0,0)\) tới điểm \((n,m)\) trong chính xác \(k\) lần lướt.

Input

• Dòng đầu tiên: Số nguyên dương \(Q\) \((Q \leq 10^4)\) - số câu hỏi
• \(Q\) dòng tiếp theo chứa số nguyên dương \(n\), \(m\), \(k\) \((n,m,k \leq 10^{18})\)

Output

• Gồm \(Q\) dòng, tại dòng thứ \(i\), in ra \(“-1”\) nếu Khôi không thể lướt từ điểm \((0,0)\) đến điểm \((n,m)\) trong chính xác \(k\) lần lướt, ngược lại in ra số lần lướt chéo nhiều nhất của Khôi

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n,m \leq 10\)
• Subtask \(1\) (\(50\%\) số điểm): \(n,m \leq 10^{18}\)

Example

3
2 2 3
4 3 7
10 1 9 

1
6
-1

Bạn được cho 2 số nguyên dương \(a, b\) \((a<b)\). Hãy tính số các số x thỏa mãn \(0\leq x <b\) và \(\gcd(a,b)=\gcd(a+x,b)\).

\(\gcd(x,y)\): Ước chung lớn nhất của \(x\) và \(y\).

Input

• Dòng đầu tiên chứa \(t\) \((1 \leq t \leq 50)\) - số câu hỏi.
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a\) và \(b\) \((1 \leq a, b \leq 10^{10})\).

Output

• Ứng với mỗi câu hỏi in ra số \(x\) cần tìm.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \((1 \leq a, b \leq 1000)\);
• Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm.

Example

3
4 9
5 10
42 9999999967 

6
1
9999999966