Bunny and Lucky are good friends. One day Bunny decided to play a game with Lucky. So he gave two numbers (a and b) and ask her to find the multiplication of a and b. She is good at mathematics, so she multiplied them and gave the answer within seconds. So he decided to add some more spicy to the problem. So he asked her to add all digits in the result until the resultant will be a single digit. Let’s consider a = 11 and b = 8, 11X8 = 88 from the result 8+8 = 16 then for 16, 1+6 = 7. So finally the answer is 7. But it is difficult her to find the vale for larger numbers.
So help her in finding the single digit value.

 

Input

Input description.

• The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows."
• The first line of each test case contains two integers a ans b

 

Output

• For each test case, output a single line containing a single digit value.

 

Constraints

Should contain all the constraints on the input data that you may have. Format it like:

• 1 = T = 10⁵
• 0 = a, b = 10¹⁸

 

Example

Input: 3 2 5 8 8 8 11 Output: 1 1 7

 

Explanation

Example case 2: 8*8 = 64 from that 6+4 = 10 the 1+0 = 1, so the answer is 1.