Bài tập

Cho một số nguyên dương \(n\) có độ dài không quá \(10^5\).

Bạn có thể thực hiện thao tác sau vô số lần: chọn một chữ số trong số đó, bình phương nó, và thay chữ số cũ bằng kết quả (kết quả phải là một chữ số nghĩa là nếu chọn một chữ số \(x\) thì \(x^2 < 10\)).

Yêu cầu: Cho số nguyên dương \(n\). Có thể biến đổi để thu được một số chia hết cho \(9\) bằng những thao tác trên không?

Input

Vào từ file BIENDOI.INP:

• Dòng đầu tiên chứa số nguyên \(t\) -- là số lượng bộ truy vấn \((1 \le t \le 10^4)\).
• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên \(n\) \((1 \le |n| \le 10^5)\).

Dữ liệu đảm bảo rằng tổng độ dài của tất cả các số trong tất cả test không vượt quá \(10^5\).

Output

Ghi ra file BIENDOI.OUT: "YES" nếu có thể và "NO" nếu không.

Example

3
123
322
333333333333

NO
YES
YES

Ở một vùng đất xa xôi, nơi những con số có linh hồn riêng, một nhà giả kim số học tên Linh đã phát minh ra một trò chơi trí tuệ với tên gọi Hợp Nhất Vô Cực.

Linh tạo ra một bảng chứa \(N\) số nguyên dương, được viết thẳng hàng trên mặt phẳng ma thuật. Mỗi số trong bảng mang một nguồn năng lượng đặc biệt, và khi hai số giống nhau đứng cạnh nhau, Linh có thể kết hợp chúng thành một số mới, lớn hơn hai số ban đầu một đơn vị.

Sau khi kết hợp, hai viên đá cũ biến mất, và thay vào ngay điểm đó bằng viên đá mới. Mục tiêu của Linh là kết hợp sao cho, số lớn nhất trên các viên đá trên dãy là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\) - số lượng các số trong bảng.
• Dòng thứ hai chứa \(N\) số nguyên dương, mỗi số không vượt quá \(40\) - các số trên bảng.

Output

• Ghi ra một số nguyên duy nhất - số lớn nhất có thể đạt được sau khi thực hiện các phép hợp nhất tối ưu.

Example

3
1 1 2

3

Scoring

• Với \(30\%\) số test, \(N \leq 1000\).
• Với \(70\%\) số test còn lại, không có ràng buộc gì thêm.

Cho ma trận \(n*n\), tính tổng các phần tử nằm trên các cột lẻ và hàng lẻ

Input

• Dòng 1: số \(n\) \((n < 100)\)

• Các dòng tiếp theo gồm các số mô tả bảng \(n*n\), giá trị tuyệt đối của các số không vượt quá 1000

Output

• In ra kết quả

Example

3
1 2 3
2 3 1
2 3 3

9

Trong Học viện mật mã, các nhà nghiên cứu đang làm việc với cấu trúc dữ liệu dạng cây phả hệ để bảo vệ thông tin. Cây phả hệ này có \(N\) nút, được đánh số từ \(1\) đến \(N\), với nút \(1\) là nút gốc.

Một nhà nghiên cứu trẻ tên là Kaito được giao nhiệm vụ phân tích một loại hoán vị "Tốt" trên cây.

Một hoán vị \(p_1, p_2, \dots, p_n\) được gọi là Tốt khi và chỉ khi, với mỗi vị trí \(i\) (\(1 \le i \le n\)), ít nhất một trong các điều kiện sau được thỏa mãn:

• Vị trí cố định: \(p_i = i\).
• Quan hệ Tổ Tiên: Nút \(p_i\) là tổ tiên của nút \(i\).
• Quan hệ Hậu Duệ: Nút \(p_i\) là hậu duệ của nút \(i\).

Bạn được yêu cầu giúp Kaito đếm số lượng hoán vị Tốt có độ dài \(N\) cho cây phả hệ đã cho, và in ra kết quả sau khi lấy modulo \(998\,244\,353\).

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 5\)) --- số lượng bộ dữ liệu thử nghiệm.

• Đối với mỗi bộ dữ liệu:

• Dòng đầu chứa số nguyên \(N\) (\(2 \le N \le 5\,000\)) --- số lượng nút trên cây.

• Dòng thứ hai chứa \(N - 1\) số nguyên \(a_2, a_3, \ldots, a_n\) (\(1 \le a_i \le i-1\)) --- \(a_i\) là cha trực tiếp của nút \(i\).

Output

Với mỗi bộ dữ liệu, in ra một số nguyên là số lượng hoán vị Tốt modulo \(998\,244\,353\).

Example

3
3
1 1
3
1 2
6
1 1 1 2 2

3
6
20

Scoring

• Subtask \(1\) (\(20\%\) số điểm) : \(N \leq 10\).
• Subtask \(2\) (\(20\%\) số điểm) : \(N \leq 20\).
• Subtask \(3\) (\(20\%\) số điểm) : \(a_i = 1\) với \(i = 2..N\) trong tất cả các bộ dữ liệu.
• Subtask \(4\) (\(20\%\) số điểm) : \(N \leq 100\).
• Subtask \(5\) (\(20\%\) số điểm) : không có ràng buộc gì thêm.