Chester has been bullied enough all his life and now he seeks revenge. His first victim being Mike, obviously! He found this very interesting question from somewhere but he doesn't have the answers to it. Now without the answers he cannot know if what Mike answered is right or wrong. The question consists of two numbers, a and b, and the answer to it is the sum of digits of a^b.
Help him find the answers so that he can successfully get his revenge!
Input: First line contains t, the number of test cases. After that t lines follow each containing a pair of space separated integers i.e. a and b.
Output: For each test case, you need to print the sum of digits in a^b.
Constraints:
1<=t<=20000
1<=a<=100
1<=b<=1000
Problem Setter: Chintan Shah
Consider the first test case. 2^10 = 1024
Now, 1 + 0 + 2 + 4 = 7 So, output for this test case is 7.
