Dinesh has been bullied enough all his life and now he seeks revenge. His first victim being Deepak, obviously! He found on e question to take revenge from deepak, but without knowing the answers of the question he would not be able to know whether deepak´s answers are correct or not. The question consists of two numbers, a and b, and the answer to it is the sum of digits of a^b (i.e - a raise to the power b). Help him to find the answers so that he can take revenge from deepak. (You should be able to write the solution for this problem in 25 minutes) Input: First line contains the number of test cases t. 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. Sample Input : 2 2 10 3 3 Sample Output : 7 9 Explanation Consider the first test case. 2^10 = 1024 Now, 1 + 0 + 2 + 4 = 7 So, output for this test case is 7.