Ankita is a maths whiz. Powers of large numbers have fascinated her for a long time. She loves them so much that when she sees two numbers A and B, she tries to find out all the odd digits in the number A raised to the power of B i.e. A^B. However she is feeling adventurous today and wants to write a program to do this for her. Being the expert programmer, you decide to help her.

Note: Only C language is allowed.

Input Format
The first line consists of the number of test cases T. Each of the following T lines thereafter comprises two numbers A and B.

Output Format
In each of the T line, print an integer N. Here, N is the number of digits that are odd in A raised to the power of B (A^B).

Constraints

1 <= T <= 10⁶
1 <= A <= 500
1 <= B <= 80