Cookie Monster

Time limit1sMemory limit128 MB

Summary

Given N and the decimal digits of N! with two adjacent digits replaced by 'ab', find the two missing digits.

Level: Medium5 of 10
Topics: Number theory, Math, Implementation
Solved: No attempts yet

Problem

Cookie Monster grew bored of the old Sesame Street and decided to emigrate to Byteland. Sadly, Byteland has no delicious sweet cookies. Unwilling to leave the digital land behind, Cookie Monster resolved to try the local specialty instead: numbers. Settling comfortably into a restaurant, he ordered a plate of fresh factorials. Unsure whether they would suit his taste, he nibbled just two adjacent digits off each one. Right then the waiter realized he had mixed up the orders: the factorials he had served were a limited edition reserved for King Byte himself, and it was the very last portion left in the storeroom! The distraught waiter must now fill the gnawed gaps, praying the king won't notice the difference. He cannot work out on his own which digits to use to plug the holes. Help the waiter and tell him which digits each gap should be filled with.

Formally, for each test case you are given an integer $N$ and the decimal representation of $N!$ ( $N$ factorial) in which two adjacent digits have been replaced by the letters a and b (always in that order). Determine the digit that replaces a and the digit that replaces b.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100$ ). Each of the next $T$ lines contains one test case, consisting of two values. The first, $N$ ( $4 \le N \le 100000$ ), is the number whose factorial is on the menu. The second is that factorial $N!$ with two adjacent digits replaced by the letters ab (always in this order).

Output

For each test case, print on its own line the two digits, separated by a single space, that should replace a and b respectively so that the resulting number is the correct factorial.

Examples4

Example 1

Input

5
12 4790ab600
13 6ab7020800
14 871782912ab
15 ab07674368000
40 815915ab3247897734345611269596115894272000000000

Expected output

Example 2
Input
```
1
4 ab
```
Expected output
```
2 4
```
Example 3
Input
```
1
5 ab0
```
Expected output
```
1 2
```

Example 4

Input

1
100 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000ab

Expected output

0 0