a-third-shape-emerges-5
Source: hackerearth
Difficulty: EASY

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^6
1 ≤ A ≤ 500
1 ≤ B ≤ 80

SAMPLE INPUT
2
5 4
3 3

SAMPLE OUTPUT
1
1

Explanation

Let's say the number A=153, B=2. So, the output should be the number of odd digits in 153^2.