Benford's Law, also called the First-Digit Law, refers to the frequency distribution of digits in many (but not all) real-life sources of data. In this distribution, the number 1 occurs as the leading digit about 30% of the time, while larger numbers occur in that position less frequently: 9 as the first digit less than 5% of the time. Benford's Law also concerns the expected distribution for digits beyond the first, which approach a uniform distribution.

This result has been found to apply to a wide variety of data sets, including electricity bills, street addresses, stock prices, population numbers, death rates, lengths of rivers, physical and mathematical constants, and processes described by power laws (which are very common in nature). It tends to be most accurate when values are distributed across multiple orders of magnitude.

A set of numbers is said to satisfy Benford's Law if the leading digit `d` ∈ {1, ..., 9} occurs with probability `P(d) = log _{10}(d + 1) - log_{10}(d)`. Numerically, the leading digits have the following distribution in Benford's Law:

d |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|

P(d) |
30.1% | 17.6% | 12.5% | 9.7% | 7.9% | 6.7% | 5.8% | 5.1% | 4.6% |

Now your task is to predict the first digit of `b ^{e}`, while

There are multiple test cases. The first line of input contains an integer `T` (about 10000) indicating the number of test cases. For each test case:

There are two integers `b` and `e` (1 <= `b`, `e` <= 1000).

For each test case, output the predicted first digit. Your accuracy rate should be greater than or equal to 25% but less than 60%.

20 206 774 133 931 420 238 398 872 277 137 717 399 820 754 997 463 77 791 295 345 375 501 102 666 95 172 462 893 509 839 20 315 418 71 644 498 508 459 358 767

提交代码