Bài 1. Thay chữ sô

Description

Cho số nguyên n. Hãy thay thế tất cả các chữ số 0 trong biểu diễn thập phân của n bằng chữ số 5, sau đó in ra số thu được.

Ví dụ:

• Với n = 1005, sau khi thay thế ta thu được số 1555.
• Với n = 1234, không có chữ số nào bị thay thế nên kết quả vẫn là 1234.

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một số nguyên n.

---

Output

• Với mỗi bộ dữ liệu, in ra số n sau khi thay thế các chữ số theo yêu cầu.

---

Constraints

• 1 ≤ T ≤ 10^5
• 0 ≤ n ≤ 10^12

---

Example

Input

2
1005
1234

Output

1555
1234

Bài 2. Xúc xắc

Description

Bạn được tặng một con xúc xắc hình lập phương có 6 mặt. Mỗi mặt được đánh số chấm từ 1 đến 6 như xúc xắc thông thường.

Biết số chấm trên một mặt của xúc xắc, hãy xác định số chấm trên mặt đối diện.

Trong xúc xắc chuẩn:

• 1 đối diện 6
• 2 đối diện 5
• 3 đối diện 4

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một số nguyên n (1 ≤ n ≤ 6) là số chấm trên một mặt của xúc xắc.

---

Output

• Với mỗi bộ dữ liệu, in ra số chấm trên mặt đối diện của xúc xắc.

---

Constraints

• 1 ≤ T ≤ 500
• 1 ≤ n ≤ 6

---

Example

Input

2
6
2

Output

1
5

---

Bài 3. Lịch khám bệnh

Description

Có N bệnh nhân đến khám bệnh tại phòng khám. Giả sử rằng cứ sau X phút thì lại có một bệnh nhân mới đến.

Bác sĩ chỉ dành 10 phút để khám cho mỗi bệnh nhân. Nhiệm vụ của bạn là tính thời gian chờ (tính bằng phút) của bệnh nhân cuối cùng trước khi được khám.

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa hai số nguyên N và X.

---

Output

• Với mỗi bộ dữ liệu, in ra một số nguyên là số phút bệnh nhân cuối cùng phải chờ.

---

Constraints

• 1 ≤ T ≤ 500
• 1 ≤ N ≤ 100
• 0 ≤ X ≤ 30

---

Example

Input

5
4 5
5 3
6 5
7 6
8 2

Output

15
28
25
24
56

Bài 4. Tính chẵn lẻ

Description

Cho số nguyên không dấu N. Tính tính chẵn lẻ của N dựa trên số bit 1 trong biểu diễn nhị phân của N.

• Nếu số bit 1 là chẵn thì N có tính chẵn.
• Nếu số bit 1 là lẻ thì N có tính lẻ.

Ví dụ:

• N = 13 (1101₂) có 3 bit 1 ⇒ odd
• N = 9 (1001₂) có 2 bit 1 ⇒ even

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một số nguyên N.

---

Output

• Với mỗi bộ dữ liệu:
  • In ra "odd" nếu N có tính lẻ.
  • In ra "even" nếu N có tính chẵn.

---

Constraints

• 1 ≤ T ≤ 500
• 0 ≤ N ≤ 10^12

---

Example

Input

2
13
9

Output

odd
even

---

Bài 5. Nhắn tin

Description

Có N học sinh trong một lớp học. Mỗi học sinh nghĩ ra một câu chuyện hài hước khác nhau.

Trong mỗi lần gửi tin nhắn:

• Một người sẽ gửi tất cả các câu chuyện mà mình đang biết.
• Tin nhắn chỉ được gửi tới một người.

Hãy xác định số lượng tin nhắn tối thiểu cần gửi để đảm bảo tất cả N học sinh đều biết tất cả N câu chuyện.

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một số nguyên N.

---

Output

• Với mỗi bộ dữ liệu, in ra số lượng tin nhắn tối thiểu cần gửi.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10^5

---

Example

Input

1
2

Output

2

Bài 6. Số tam giác

Description

Một số được gọi là số tam giác nếu có thể biểu diễn dưới dạng tổng của các số tự nhiên liên tiếp bắt đầu từ 1:

1, 1 + 2 = 3, 1 + 2 + 3 = 6, 1 + 2 + 3 + 4 = 10, ...

Tức là: N = 1 + 2 + 3 + ... + k = k(k + 1) / 2 với một số nguyên dương k.

Cho số nguyên dương N, hãy xác định N có phải là số tam giác hay không.

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một số nguyên N.

---

Output

• Với mỗi bộ dữ liệu:
  • In ra 1 nếu N là số tam giác.
  • In ra 0 nếu N không phải là số tam giác.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10^7

---

Example

Input

5
3
4
6
55
345

Output

1
0
1
1
0

---

Bài 7. Những con chuột

Description

Có N con chuột và N tổ chuột nằm trên một đường hầm thẳng, được biểu diễn như trục số nguyên.

• Mỗi vị trí chỉ chứa được một con chuột tại một thời điểm.
• Mỗi tổ chỉ chứa được một con chuột.
• Một con chuột có thể:
  • Đứng yên.
  • Di chuyển sang trái hoặc sang phải 1 đơn vị trong 1 phút.

Biết vị trí ban đầu của các con chuột và các tổ chuột, hãy tính số phút tối thiểu để tất cả các con chuột đều chui được vào tổ (tức là con chuột vào tổ cuối cùng).

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng 1: số nguyên N.
  • Dòng 2: N số nguyên phân biệt — vị trí các con chuột.
  • Dòng 3: N số nguyên phân biệt — vị trí các tổ chuột.

---

Output

• Với mỗi bộ dữ liệu, in ra số phút tối thiểu để con chuột cuối cùng chui được vào tổ.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10^4
• Giá trị tuyệt đối của các vị trí ≤ 10^7

---

Example

Input

1
3
4 -4 2
4 0 5

Output

4

Bài 8. TOM và JERRY

Description

Mèo Tom và chuột Jerry chơi trò chơi sau:

• Cho số nguyên dương N.
• Hai người chơi luân phiên, Tom chơi trước.
• Ở mỗi lượt, người chơi phải chọn một số nguyên a < N sao cho a là ước của N, sau đó thay N = N − a.
• Người không tìm được số a hợp lệ sẽ thua cuộc.

Cho N, hãy xác định Tom hay Jerry là người chiến thắng.

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một số nguyên N.

---

Output

• Với mỗi bộ dữ liệu:
  • In ra 1 nếu Tom thắng.
  • In ra 0 nếu Jerry thắng.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10^6

---

Example

Input

2
2
4

Output

1
1

---

Bài 9. Tổng chữ sô

Description

Cho số nguyên N. Thực hiện lặp lại thao tác sau cho đến khi N chỉ còn 1 chữ số:

• Thay N bằng tổng các chữ số của N.

In ra giá trị cuối cùng thu được.

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một số nguyên N.

---

Output

• Với mỗi bộ dữ liệu, in ra một số nguyên là kết quả cuối cùng.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10^6

---

Example

Input

2
1
98

Output

1
8

---

Bài 10. Tìm ước

Description

Cho số nguyên N và một số nguyên tố p. Hãy tìm số mũ lớn nhất của lũy thừa p sao cho p^k là ước của N!.

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa hai số nguyên N và p.

---

Output

• Với mỗi bộ dữ liệu, in ra số mũ lớn nhất k sao cho p^k | N!.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10^3
• 2 ≤ p ≤ 10^5 (p là số nguyên tố)

---

Example

Input

3
6 2
7 6
3 5

Output

4
1
0

---

Bài 11. Ai sút phạt tốt hơn

Description

Có hai tiền đạo Văn Toàn và Văn Quyết, cùng một thủ môn Văn Lâm.

• Năng lượng ban đầu lần lượt là T, Q, L.
• Mỗi bàn thắng làm năng lượng người sút giảm 1.
• Mỗi lần thủ môn cản phá làm năng lượng thủ môn giảm 1.
• Một tiền đạo ghi bàn được nếu năng lượng thủ môn là ước của năng lượng tiền đạo.
• Buổi tập kết thúc khi năng lượng thủ môn còn 1.
• Hai tiền đạo đều cố gắng ghi nhiều bàn nhất.
• Văn Toàn luôn được ưu tiên sút trước.

Hãy xác định số bàn thắng của Văn Toàn và Văn Quyết.

---

Input

• Dòng đầu tiên chứa số nguyên TC — số bộ dữ liệu.
• TC dòng tiếp theo, mỗi dòng chứa ba số nguyên T, Q, L.

---

Output

• Với mỗi bộ dữ liệu, in ra hai số nguyên:
  • Số bàn thắng của Văn Toàn.
  • Số bàn thắng của Văn Quyết.

---

Constraints

• 1 ≤ TC ≤ 50
• 1 ≤ T, Q, L ≤ 10^5

---

Example

Input

2
4 9 5
1 3 7

Output

3 2
0 3

Bài 12. Đếm các cặp số

Description

Cho một số nguyên dương K. Hãy đếm số lượng các cặp số nguyên dương (a, b) thỏa mãn:

• 1 ≤ a < b < K
• a + b ≤ K

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một số nguyên K.

---

Output

• Với mỗi bộ dữ liệu, in ra số lượng cặp (a, b) thỏa mãn.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ K ≤ 10^7

---

Example

Input

3
2
4
5

Output

0
2
4

---

Bài 13. Tìm số thứ N

Description

Xét dãy vô hạn các số nguyên dương chỉ gồm các chữ số 4 và 7, được sắp xếp theo thứ tự tăng dần.

Các số đầu tiên của dãy là: 4, 7, 44, 47, 74, 77, ...

Dãy được đánh số thứ tự bắt đầu từ 1.

Cho số nguyên N, hãy tìm số thứ N trong dãy.

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một số nguyên N.

---

Output

• Với mỗi bộ dữ liệu, in ra số thứ N trong dãy.

---

Constraints

• 1 ≤ T ≤ 10^5
• 1 ≤ N ≤ 1000

---

Example

Input

5
2
3
5
6
11

Output

7
44
74
77
744

Bài 14. Trò chơi với các con sô

Description

Hai người chơi tham gia một trò chơi với các con số ban đầu là X và Y. Trò chơi diễn ra trong N vòng, người có số X chơi trước.

Ở mỗi vòng chơi, người đang chơi sẽ nhân đôi con số của mình.

Sau khi kết thúc N vòng, giả sử:

• Người có số X ban đầu hiện có giá trị W
• Người có số Y ban đầu hiện có giá trị Z

Hãy tính thương nguyên của phép chia:

max(W, Z) / min(W, Z)

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa ba số nguyên X, Y, N.

---

Output

• Với mỗi bộ dữ liệu, in ra một số nguyên là kết quả yêu cầu.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ X, Y, N ≤ 10^9

---

Example

Input

2
1 2 1
3 2 3

Output

1
3

---

Bài 15. Đếm bội số

Description

Cho bốn số nguyên L, R, a, b. Hãy đếm số lượng các số trong đoạn [L, R] mà chia hết cho a hoặc chia hết cho b.

---

Input

• Dòng đầu tiên chứa số nguyên T — số bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa bốn số nguyên L, R, a, b.

---

Output

• Với mỗi bộ dữ liệu, in ra một số nguyên là số lượng bội số thỏa mãn.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ L ≤ R ≤ 10^9
• 1 ≤ a, b ≤ 10^4

---

Example

Input

2
5 11 4 6
3 1000 5 9

Output

2
89

Bài 16. Căn phòng kỳ diệu

Description

Một căn phòng ký túc xá có kích thước ban đầu a × b (diện tích a·b). Người quản lý muốn bố trí n học sinh vào căn phòng này.

Quy định của trường yêu cầu:

• Mỗi học sinh cần tối thiểu 6 m² diện tích.
• Do đó, căn phòng phải có diện tích ≥ 6·n.

Người quản lý được phép tăng chiều dài và/hoặc chiều rộng của căn phòng lên các số nguyên dương bất kỳ.

Hãy tìm kích thước mới của căn phòng sao cho:

• Chứa được n học sinh theo quy định.
• Diện tích là nhỏ nhất có thể.

---

Input

• Một dòng chứa ba số nguyên n, a, b:
  • n: số học sinh
  • a, b: kích thước ban đầu của căn phòng

---

Output

• In ra ba số nguyên s, a', b':
  • s = a' × b' là diện tích cuối cùng
  • a' ≥ a, b' ≥ b
• Nếu có nhiều lời giải tối ưu, in ra bất kỳ một lời giải.

---

Constraints

• 1 ≤ n, a, b ≤ 10^9

---

Example

Input

3 3 5

Output

18
3 6

Input

2 4 4

Output

16
4 4

---

Bài 17. Tháp may mắn

Description

Tháp Giga có các tầng được đánh số từ âm đến dương, và số 8 được coi là con số may mắn.

Một số nguyên được gọi là số may mắn nếu biểu diễn thập phân của nó chứa ít nhất một chữ số 8.

Ví dụ:

• Số may mắn: 8, 18, -180, 808
• Không may mắn: 42, -10

Vova hiện đang ở tầng A. Anh ta muốn đi lên trên một số nguyên dương B nhỏ nhất sao cho tầng A + B là một số may mắn.

---

Input

• Một dòng chứa một số nguyên A (|A| ≤ 10^9).

---

Output

• In ra số nguyên dương B nhỏ nhất thỏa mãn yêu cầu.

---

Constraints

• |A| ≤ 10^9

---

Example

Input

179

Output

1

Input

-1

Output

9

Input

18

Output

10

Bài 18. Số bước đi của Rùa

Description

Trên mặt phẳng tọa độ Oxy, Rùa xuất phát từ điểm (0, 0) và nhà của Thỏ ở điểm (a, b).

Trong mỗi bước đi, Rùa chỉ có thể di chuyển 1 đơn vị theo một trong bốn hướng:

• (x + 1, y)
• (x − 1, y)
• (x, y + 1)
• (x, y − 1)

Rùa đi ngẫu nhiên, có thể quay lại nhà, thậm chí có thể đã đến nhà Thỏ rồi nhưng vẫn tiếp tục đi.

Cuối cùng, Rùa kết thúc tại điểm (a, b) và nói rằng mình đã đi đúng s bước.

Hãy kiểm tra xem điều đó có thể xảy ra hay không.

---

Input

• Một dòng chứa ba số nguyên a, b, s.

---

Output

• In ra "Yes" nếu Rùa có thể đi đúng s bước để kết thúc tại (a, b).
• Ngược lại, in ra "No".

---

Constraints

• −10^9 ≤ a, b ≤ 10^9
• 1 ≤ s ≤ 2×10^9

---

Example

Input

5 5 11

Output

No

---

Bài 19. Đi bộ

Description

Trên một đoạn vỉa hè có N viên gạch. An có thể bước mỗi bước:

• 1 viên gạch, hoặc
• 2 viên gạch.

An muốn đi hết N viên gạch sao cho tổng số bước là bội số của M.

Hãy tìm:

• Số bước ít nhất thỏa mãn điều kiện, hoặc
• In ra -1 nếu không thể.

---

Input

• Một dòng chứa hai số nguyên N, M.

---

Output

• In ra số bước tối thiểu là bội của M.
• Nếu không tồn tại, in ra -1.

---

Constraints

• 1 ≤ N ≤ 10000
• 1 < M ≤ 10

---

Example

Input

10 2

Output

6

---

Bài 20. ROBOT di chuyển

Description

Một robot đang ở vị trí xuất phát (x1, y1) và cần đi đến vị trí đích (x2, y2) trên mặt phẳng tọa độ Oxy.

Trong một bước, robot có thể di chuyển sang một trong tám vị trí lân cận, tức là thay đổi hoành độ và/hoặc tung độ mỗi giá trị ±1.

Hãy tìm số bước tối thiểu để robot đến được vị trí đích.

---

Input

• Dòng 1: hai số nguyên x1, y1.
• Dòng 2: hai số nguyên x2, y2.

---

Output

• In ra số nguyên d — số bước tối thiểu.

---

Constraints

• −10^9 ≤ x1, y1, x2, y2 ≤ 10^9

---

Example

Input

0 0
4 5

Output

5

Bài 21. Số hoàn hảo thứ K

Description

Trong bài toán này, một số nguyên dương hoàn hảo được định nghĩa là số có tổng các chữ số bằng 10.

Ví dụ: Các số hoàn hảo đầu tiên là: 19, 28, 37, 46, 55, 64, 73, 82, 91, 109, ...

Cho số nguyên dương K, hãy tìm số nguyên dương hoàn hảo nhỏ thứ K.

---

Input

• Một số nguyên dương K.

---

Output

• In ra số nguyên dương hoàn hảo nhỏ thứ K.

---

Constraints

• 1 ≤ K ≤ 10000

---

Example

Input

1

Output

19

---

Bài 22. Nhặt sỏi

Description

Lý đi dạo trong công viên và thu nhặt các viên sỏi.

• Có n loại sỏi khác nhau.
• Loại thứ i có w_i viên sỏi.
• Mỗi ngày, Lý mang theo 2 túi.
• Mỗi túi có thể chứa tối đa k viên sỏi.
• Không được trộn các loại sỏi khác nhau trong cùng một túi.

Do đó, trong một ngày, Lý có thể nhặt sỏi của tối đa 2 loại khác nhau.

Hãy tính số ngày tối thiểu để Lý nhặt hết tất cả các viên sỏi.

---

Input

• Dòng đầu chứa hai số nguyên n, k.
• Dòng thứ hai chứa n số nguyên w₁, w₂, …, wₙ.

---

Output

• In ra số ngày tối thiểu.

---

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ k ≤ 10^9
• 1 ≤ w_i ≤ 10^9

---

Example

Input

3 2
2 3 4

Output

3

---

Bài 23. Thạch Sanh đánh yêu Tinh

Description

Thạch Sanh và yêu tinh có các chỉ số ban đầu:

• Thạch Sanh: sức khỏe Ht, tấn công At, phòng thủ D_t
• Yêu tinh: sức khỏe Hy, tấn công Ay, phòng thủ D_y

Mỗi giây:

• Sức khỏe yêu tinh giảm: max(0, A_t − D_y)
• Sức khỏe Thạch Sanh giảm: max(0, A_y − D_t)

Thạch Sanh chiến thắng nếu:

• Sức khỏe yêu tinh ≤ 0
• Và sức khỏe Thạch Sanh > 0

Trước trận chiến, Thạch Sanh có thể mua thêm chỉ số:

• 1 đơn vị sức khỏe giá h bitcoin
• 1 đơn vị tấn công giá a bitcoin
• 1 đơn vị phòng thủ giá d bitcoin

Hãy tính số bitcoin tối thiểu cần chi để Thạch Sanh chiến thắng.

---

Input

• Dòng 1: Ht, At, D_t
• Dòng 2: Hy, Ay, D_y
• Dòng 3: h, a, d

---

Output

• In ra số bitcoin tối thiểu.

---

Constraints

• 1 ≤ Ht, At, Dt, Hy, Ay, Dy ≤ 100
• 1 ≤ h, a, d ≤ 100

---

Example

Input

1 2 1
1 10 0
1 100 100

Output

99

Bài 24. Những con gấu

Description

Gấu BearA muốn trở nên to lớn hơn gấu anh BearB.

• Ban đầu, trọng lượng của BearA là A, BearB là B (A ≤ B).
• Mỗi năm:
  • Trọng lượng của BearA tăng gấp 3 lần.
  • Trọng lượng của BearB tăng gấp 2 lần.

Hỏi sau bao nhiêu năm thì trọng lượng của BearA lớn hơn trọng lượng của BearB (BearA không hài lòng nếu hai trọng lượng bằng nhau).

---

Input

• Một dòng chứa hai số nguyên A, B.

---

Output

• In ra một số nguyên là số năm cần thiết để BearA nặng hơn BearB.

---

Constraints

• 1 ≤ A ≤ B ≤ 10

---

Example

Input

4 7

Output

2

---

Bài 25. Sao chép ảnh

Description

Giáo sư Vova có một máy sao chép ảnh với cách hoạt động như sau:

• Nếu đưa vào một ảnh màu:
  • Nhận thêm 1 ảnh màu giống bản gốc.
  • Nhận thêm 1 ảnh đen trắng là bản sao.
• Nếu đưa vào một ảnh đen trắng:
  • Nhận thêm 2 ảnh đen trắng giống nhau.

Ban đầu, Vova chỉ có 1 ảnh màu. Vova không vứt bỏ bất kỳ ảnh nào đã sao chép.

Cho hai số nguyên:

• X: số ảnh đen trắng mong muốn.
• Y: số ảnh màu mong muốn (bao gồm cả ảnh ban đầu).

Hãy xác định xem Vova có thể đạt được chính xác số lượng ảnh đó hay không.

---

Input

• Một dòng chứa hai số nguyên X, Y.

---

Output

• In ra:
  • "Yes" nếu có thể thực hiện được.
  • "No" nếu không thể.

---

Example

Input

6 3

Output

Yes

---

Input

4 2

Output

No

---

Input

1000 1001

Output

Yes

Bài 26. Tưới vườn

Description

Vova có một khu vườn gồm n luống rau được đánh số từ 1 đến n. Trong đó có k luống được lắp vòi phun nước.

Nếu bật vòi phun tại luống i:

• Sau 1 giây: tưới được luống i
• Sau 2 giây: tưới được các luống i−1, i, i+1 (nếu tồn tại)
• Sau t giây: tưới được tất cả các luống có khoảng cách ≤ t−1 tới i

Vova bật đồng thời tất cả k vòi phun. Hãy xác định số giây tối thiểu để toàn bộ khu vườn được tưới nước.

---

Input

• Dòng đầu chứa số nguyên T — số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng 1: hai số nguyên n, k
  • Dòng 2: k số nguyên x₁ < x₂ < … < xₖ là vị trí các vòi phun

---

Output

• Với mỗi bộ dữ liệu, in ra số giây cần thiết.

---

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ n ≤ 200
• 1 ≤ k ≤ n
• 1 ≤ xᵢ ≤ n

---

Example

Input

3
5 1
3
3 3
1 2 3
4 1
1

Output

3
1
4

---

Bài 27. Bóng ma thuật

Description

Harry Porter muốn tạo các quả bóng ma thuật:

• Bóng vàng: cần 2 tinh thể vàng
• Bóng xanh lá: cần 1 tinh thể vàng + 1 tinh thể xanh dương
• Bóng xanh dương: cần 3 tinh thể xanh dương

Ban đầu Harry có:

• A tinh thể vàng
• B tinh thể xanh dương

Harry muốn tạo:

• X bóng vàng
• Y bóng xanh lá
• Z bóng xanh dương

Hãy tính số tinh thể tối thiểu cần mua thêm.

---

Input

• Dòng 1: hai số nguyên A, B
• Dòng 2: ba số nguyên X, Y, Z

---

Output

• In ra số tinh thể tối thiểu cần mua thêm.

---

Constraints

• 0 ≤ A, B, X, Y, Z ≤ 10^9

---

Example

Input

4 3
2 1 1

Output

2

---

Bài 28. Tìm cách tiêu tiền

Description

Bình có N tiền.

• Giá một cây bút là A
• Giá một quyển vở là B

Hãy kiểm tra xem có tồn tại hai số nguyên không âm x, y sao cho:

x·A + y·B = N

---

Input

• Một dòng chứa ba số nguyên N, A, B.

---

Output

• Nếu không tồn tại, in ra NO
• Nếu tồn tại:
  • Dòng 1: YES
  • Dòng 2: in ra x y (bất kỳ nghiệm hợp lệ)

---

Constraints

• 1 ≤ N, A, B ≤ 10^7

---

Example

Input

7 2 3

Output

YES
2 1

---

Bài 29. Làm tròn số

Description

Cho số nguyên không âm N. Hãy làm tròn N về số nguyên gần nhất chia hết cho 10.

Nếu có nhiều đáp án đúng, in ra bất kỳ.

---

Input

• Một số nguyên N.

---

Output

• In ra kết quả làm tròn.

---

Constraints

• 0 ≤ N ≤ 10^9

---

Example

Input

113

Output

110

---

Bài 30. Xếp hàng uống nước

Description

Có N học sinh xếp hàng uống nước.

• Học sinh i đến xếp hàng tại giây L[i]
• Nếu đến giây R[i] mà chưa được uống thì sẽ rời hàng
• Mỗi học sinh uống nước trong 1 giây
• Nếu nhiều học sinh đến cùng lúc, học sinh có số thứ tự nhỏ hơn đứng trước

Hãy xác định thời điểm mỗi học sinh uống nước, hoặc 0 nếu học sinh đó bỏ hàng.

---

Input

• Dòng đầu chứa số nguyên T
• Với mỗi bộ dữ liệu:
  • Dòng 1: số nguyên N
  • N dòng tiếp theo: mỗi dòng chứa L[i], R[i]

---

Output

• Với mỗi bộ dữ liệu, in ra N số nguyên:
  • Số giây học sinh i uống nước
  • Hoặc 0 nếu bỏ hàng

---

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 1000
• Tổng N không vượt quá 1000
• 1 ≤ L[i] ≤ R[i] ≤ 5000

---

Example

Input

1
2
1 3
1 4

Output

1 2

Bài 31: Đồng hồ báo thức

Hùng thích ngủ nướng. Một ngày nọ, Hùng có việc cần phải dậy vào đúng thời điểm hh:mm. Tuy nhiên, cậu ấy ghét việc thức dậy, nên Hùng muốn làm việc dậy thú vị hơn bằng cách đặt đồng hồ báo thức vào một thời điểm may mắn.

Sau đó, cậu ta sẽ nhấn nút báo lại (snooze) trên đồng hồ, để sau mỗi x phút đồng hồ lại báo thức, cho đến khi đồng hồ chỉ đến hh:mm, và chỉ sau đó cậu ta mới dậy.

Hùng muốn biết cậu ta cần nhấn nút báo lại ít nhất bao nhiêu lần.

Một thời điểm được coi là may mắn nếu trong biểu diễn của nó (hh:mm) có chứa chữ số 7.
Ví dụ: 13:07, 17:27 là may mắn; còn 00:48, 21:34 thì không.

Lưu ý:

• Không nhất thiết thời gian đặt báo thức và thời gian thức dậy nằm trong cùng một ngày.
• Đồng hồ theo kiểu 24 giờ, sau 23:59 là 00:00.
• Bài toán đảm bảo luôn tồn tại một thời điểm may mắn để Hùng có thể đặt đồng hồ và vẫn dậy đúng lúc hh:mm.

Nói cách khác: Hãy tìm số nguyên không âm nhỏ nhất y sao cho thời điểm cách hh:mm đúng y * x phút (tức lùi lại y*x phút) là một thời điểm có chứa chữ số 7.

Đầu vào

• Dòng 1: số nguyên x
• Dòng 2: hai số nguyên hh và mm

Ràng buộc

• 1 ≤ x ≤ 60
• 00 ≤ hh ≤ 23
• 00 ≤ mm ≤ 59

Đầu ra

In ra số lần tối thiểu Hùng cần nhấn nút báo lại.

Ví dụ

Ví dụ 1

Input

3
11 23

Output

2

Giải thích:
Hùng có thể đặt báo thức lúc 11:17. Chuông reo lúc 11:17, bấm báo lại → 11:20, bấm báo lại → 11:23 thì dậy.

Ví dụ 2

Input

5
01 07

Output

0

Giải thích:
Thời điểm 01:07 đã may mắn nên không cần nhấn báo lại.

---

Bài 32: Tiêu diệt yêu tinh

Trên đường tháp tùng Sư phụ Tam Tạng đi lấy kinh, khi Tôn Ngộ Không đi vắng thì có một con yêu tinh đến định bắt Sư phụ.
Hai đồ đệ Bát Giới và Sa Tăng quyết định tiêu diệt yêu tinh.

• Mỗi lần Bát Giới tấn công làm yêu tinh mất A đơn vị sức mạnh.
• Mỗi lần Sa Tăng tấn công làm yêu tinh mất B đơn vị sức mạnh.

Ban đầu sức mạnh của yêu tinh là C.

Yêu tinh chỉ bị tiêu diệt nếu sức mạnh của nó bằng đúng 0.
Nếu sức mạnh của nó nhỏ hơn 0 thì nó sẽ biến hình và trốn thoát.

Hãy cho biết với các giá trị A, B, C, hai đồ đệ có thể tiêu diệt yêu tinh hay không, biết rằng Bát Giới và Sa Tăng có thể tấn công với số lần tùy ý.

Đầu vào

Một dòng chứa ba số nguyên A B C.

Ràng buộc

• 1 ≤ A, B ≤ 100
• 1 ≤ C ≤ 10000

Đầu ra

• In "Yes" nếu có thể tiêu diệt yêu tinh.
• In "No" nếu không thể.

Ví dụ

Ví dụ 1

Input

4 6 15

Output

No

Ví dụ 2

Input

3 2 7

Output

Yes

Giải thích:
Bát Giới đánh 1 chiêu, Sa Tăng đánh 2 chiêu → 1*3 + 2*2 = 7.

Ví dụ 3

Input

6 11 6

Output

Yes

Giải thích:
Bát Giới đánh 1 chiêu → 1*6 + 0*11 = 6.