H. Baker Street Cipher Wheel
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

London, 1891. Sherlock Holmes wants to send a secret message to Dr. Watson.

There are $$$N$$$ identical iron posts in a courtyard. Holmes may write one digit (0–9) on any post and may leave some posts blank. Later, Watson will see the courtyard, but because of fog and moved lanterns, he cannot know the order of the posts. He only knows how many times each digit appears. The order does not matter.

Before Watson arrives, a clerk may use a cipher wheel. Every time the wheel is used, each written digit $$$d$$$ is replaced by $$$ d \rightarrow (a \cdot d + b) \bmod 10 $$$ where:

  • $$$a$$$ is chosen from a given set $$$S_a \subseteq \{1,3,7,9\}$$$,
  • $$$b$$$ is chosen from a given set $$$S_b \subseteq \{0,1,\dots,9\}$$$.

The wheel may be used any number of times (possibly zero). Each use can choose any $$$a \in S_a$$$ and any $$$b \in S_b$$$. So the final effect is a composition of such transformations.

Holmes and Watson know $$$N$$$, $$$S_a$$$, and $$$S_b$$$, but Watson does not know which transformations were applied.

Because Watson only sees digit counts:

  • A writing is completely described by a multiset of digits.
  • Its size is between $$$1$$$ and $$$N$$$.

Two writings are indistinguishable if one can be obtained from the other by applying some allowed sequence of cipher wheel operations (and then shuffling).

Your task is to compute how many different secrets Holmes can encode so that Watson can always decode them correctly.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

Each test case contains one line with:

  • an integer $$$N$$$ ($$$1 \le N \le 350$$$),
  • a string Sa — the elements of $$$S_a$$$,
  • a string Sb — the elements of $$$S_b$$$.

The strings satisfy:

  • Sa is non-empty and consists only of characters from 1, 3, 7, 9,
  • Sb is non-empty and consists only of characters from 0 to 9,
  • all characters in each string are distinct.
Output

For each test case, output one integer — the maximum number of different secrets Holmes can encode.

It is guaranteed that the answer fits in a signed 64-bit integer.

Example
Input
3
3 1 0
3 19 05
3 1379 0123456789
Output
285
79
13
Note

In the first test case, only the identity transformation is possible, so all non-empty digit multisets of size at most $$$3$$$ are distinguishable.

In the last test case, the full affine group acts on the digits, so many different writings become indistinguishable, and the number of secrets is much smaller.