#include

#include<math.h>

using namespace std;

int main() {

int t;

cin>>t;

while(t–){

int x,m,c=0,d=0,b=0,y=0;

cin>>x>>m;

c=x;

while(c>0){

d=c%10;

c/=10;

y=pow(d,m);

b=b*10+(y%10);

}

if(b%7==0)

cout<<“yes\n”;

else

cout<<“no\n”;

}

return 0;

}

Quick! You need to solve this problem in order to help the Chef get an A on a math exam! The problem is as follows:

You are given two integers: X and M. Now, you need to replace each digit of X (let’s call them di) with dMimod10. Let’s call the new number Y and reverse it (explained in note 3). Check whether Y is divisible by 7.

Note 1: dMi=di⋅di⋅…⋅di (M times) - definition of di to the power of M. Special case: dMi=1, when M=0

Note 2: Xmod10 is the remainder of division X by 10, where X is some integer number.

Note 3: Reversing an integer is an operation that reverse the order of its digits and erase leading zeros. For example: 123 when reversed becomes 321 and 450 when reversed becomes 54.

Input Format

The first line of the input contains a single integer: T - representing the number of test cases

Each of the test cases contains a line with two space-separated integers: X and M

Output Format

For each test case output a line containing either “YES” or “NO” depending on whether Y is divisible by 7.

You may print each character of the string in uppercase or lowercase (for example: the strings “yes”, “YeS”, “YES” will be treated as the same strings).

Constraints

1≤T≤500

1≤X≤109

0≤M≤100

Sample Input 1

1

123 2

Sample Output 1

NO

Explanation

After squaring all the digits the number we get is 149 and when we reverse it, it becomes 941. 941 is not divisible by 7.

Sample Input 2

1

123 4

Sample Output 2

YES

Explanation

1 to the power of 4 is 1. 2 to the power of 4 is 16mod10=6. 3 to the power of 4 modulo 10 is 1. So the number we get is 161 and it stays the same when reversed. 161 is divisible by 7.