Số siêu may mắn

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 900 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một số nguyên dương được gọi là số siêu may mắn nếu thỏa mãn đồng thời hai điều kiện:

Tổng các chữ số của số đó là một số nguyên tố.
Bình phương của tổng các chữ số có số chữ số đúng bằng \(k\).

Input

Dòng đầu tiên chứa số nguyên \(q\) (\(1 \le q \le 10^5\)).
\(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(n\) và \(k\) (\(1 \le n \le 10^{18}, 1 \le k \le 18\)).

Output

Với mỗi truy vấn, in ra YES nếu \(n\) là số siêu may mắn, ngược lại in ra NO.

Example

Test 1

Input

Output

YES
NO
NO

Note

Với \(n = 23, k = 2\):
- Tổng các chữ số: \(2 + 3 = 5\) (là số nguyên tố).
- Bình phương tổng các chữ số: \(5^2 = 25\) (có \(2\) chữ số, khớp với \(k = 2\)).
- Kết quả: YES.
Với \(n = 11, k = 2\):
- Tổng các chữ số: \(1 + 1 = 2\) (là số nguyên tố).
- Bình phương tổng các chữ số: \(2^2 = 4\) (có \(1\) chữ số, khác với \(k = 2\)).
- Kết quả: NO.
Với \(n = 23, k = 1\):
- Tổng các chữ số: \(2 + 3 = 5\) (là số nguyên tố).
- Bình phương tổng các chữ số: \(5^2 = 25\) (có \(2\) chữ số, khác với \(k = 1\)).
- Kết quả: NO.

Scoring

Subtask \(1\) (\(20\%\) số điểm): \(q \le 100, n \le 10^5\).
Subtask \(2\) (\(30\%\) số điểm): \(q \le 10^4, n \le 10^{12}\).
Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Bình luận (1)

Tải bình luận...