题目描述
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.
输入格式
见题面
输出格式
见题面