Background

$\kern{75pt}$

The cute Cirno met Doremy Sweet in the classroom of the terakoya. Kind-hearted Doremy told her the questions for the final exam: as long as she solved them, she could avoid being headbutted by Teacher Keine. Excited, Cirno said goodbye to Doremy, but suddenly realized she was already in the final exam room! However, Cirno is just too dumb. When she woke up, she forgot everything Doremy had told her, and only remembered that the paper had lots of ⑨.

Now Cirno is already taking the exam. You can use the fairy link of ⑨ to answer her questions, to ease her sadness of forgetting the answers. Can you help her?

Friendly reminder: cheating in exams is not right.

Problem Description

Cirno defines a positive decimal integer as a "$k$-th order genius number" if and only if the number of digits of this integer is a multiple of $k$, and every digit is $9$. For example, $9999$ is a $2$-th order genius number, while $999$ is not a $2$-th order genius number; but it is a $1$-st order genius number, and also a $3$-rd order genius number.

Cirno gives you $t$ queries. Each query contains two integers $n$ and $k$. She wants you to tell her whether $n$ can be decomposed into the sum of several $k$-th order genius numbers.

Input Format

• The first line contains an integer $t$, representing the number of queries.
• The next $t$ lines each contain two integers $k$ and $n$, representing one query.

Output Format

• Output $t$ lines in total. If the answer to the corresponding query is yes, output one line with the string aya; otherwise output one line with the string baka.

2
1 999
2 999

aya
baka

Hint

This problem has a total of $20$ test points, and each test point is worth $5$ points. The final score is the sum of the scores of all test points.

$$\def\n{\text{No special limits}} \def\arraystretch{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Task} & \bm t= & \bm {n_i \le} & \bm {k_i \le} \cr\hline 1 & 1 & 233 & 1 \cr\hline 2\sim 6 & 1 & 10^3 & 1 \cr\hline 7\sim 8 & 10 & 10^9 & 1 \cr\hline 9 & 10^3 & 10^9 & 1 \cr\hline 10 & 10^3 & 10^{18} & 1 \cr\hline 11\sim 20 & 10^3 & 10^{18} & 10 \cr\hline \end{array}$$

For all data, it holds that $1\le t\le 10^3$, $1\le n_i\le 10^{18}$, $1\le k_i\le 10$.

Translated by ChatGPT 5