Trong phòng thí nghiệm nano, các nhà khoa học đang nghiên cứu một quy trình tổng hợp vật chất mang tên "nhân hai cộng một". Quy trình này biến đổi một cấu trúc vật chất (được mô tả bằng một xâu ký tự \(a\)) theo nguyên tắc sau:

1. Nhân đôi: Tạo ra một bản sao của xâu \(a\) và gắn vào ngay sau xâu gốc (thu được \(a + a\)).
2. Cộng một: Gắn thêm một nguyên tử mới (là một ký tự \(c\) bất kỳ trong bảng chữ cái) vào cuối xâu vừa tạo.

Ví dụ: Từ xâu ab, quy trình sẽ tạo ra ab + ab + x = ababx.

Mọi cấu trúc đều bắt đầu từ "hư không" (xâu rỗng). Nhà nghiên cứu An vừa tìm thấy một số mẫu vật lạ và muốn kiểm tra nguồn gốc của chúng. Với mỗi mẫu vật (xâu \(s\)), An có hai loại câu hỏi:

• Loại 1: Xâu \(s\) này có phải là kết quả thuần túy của quy trình trên (xuất phát từ xâu rỗng) hay không?
• Loại 2: Nếu ta được phép sắp xếp lại vị trí các nguyên tử trong \(s\) tùy ý, liệu có thể tạo ra một cấu trúc đúng chuẩn quy trình trên (có thể được tạo từ xâu rỗng) hay không?

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 10\)) là số lượng mẫu vật cần kiểm tra.
• \(T\) dòng tiếp theo, mỗi dòng chứa thông tin về một mẫu vật gồm:
  • Một xâu ký tự \(s\) chỉ gồm các chữ cái in thường (độ dài không quá \(270\,000\) ký tự).
  • Một số nguyên \(\theta \in \{1, 2\}\) biểu thị loại câu hỏi (\(\theta = 1\) là hỏi Loại 1, \(\theta = 2\) là hỏi Loại 2).

Output

• Với mỗi mẫu vật, in ra YES nếu câu trả lời là có thể, hoặc NO nếu không thể.

Example

4
a 1
aab 1
aba 1
aba 2

YES
YES
NO
YES

Subtask

• Subtask 1: \(30\%\) số điểm có độ dài xâu \(s \le 3\) và \(\theta = 1\).
• Subtask 2: \(20\%\) số điểm khác có \(\theta = 1\).
• Subtask 3: \(30\%\) số điểm khác có độ dài xâu \(s \le 3\).
• Subtask 4: \(20\%\) số điểm còn lại không có giới hạn gì thêm.