There are n+1 strings of length n --- . The characters in the string are numbered from 0 to n-1 (from left to right). The character i of is the digit i modulo 10.

For example, if n = 5, is "01234", and if n=14, is "01234567890123".

You are given a permutation of  : p[0], p[1], ..., p[n-1] and a sequence of digits of length n : d[0], d[1], ..., d[n-1]. can be obtained by replacing character p[i] of  with digit d[i]. Note that if d[i] is as same as the character p[i] of , then will be the same as .

Now we want to sort these n+1 strings. The string with index i should be placed to the left of string with index j if and only if is lexicographically smaller than , or equal to and i < j. Let be the new position of string from the left, that is,  is the i-th string from the left after sorting. (Positions are number start from 0.)

For example, if n = 5, p = [4, 3, 0, 1, 2] and d = [5, 0, 0, 0, 0], then "01234", "01235", "01205", "01205", "00205", "00005". So , , , , , and .

Please calculate all for i from 0 to n.

The first line contains one integer t () --- the number of test cases.
 
 The first line of each test contains one positive integer n ().
 
 The second line of each test contains four integers  (). Use the following pseudocode for generating the p.
 
seed =  for i = 0 to n - 1:
    p[i] = i
for i = 1 to n - 1:
    swap the value of  and p[i]
    seed = (seed *  + ) modulo  
 The third line of each test contains four integers  (). Use the following pseudocode for generating the d.
 
 
seed =  for i = 0 to n-1:
    d[i] = seed modulo 10
    seed = (seed *  + ) modulo 
 
 The sum of n across the test cases doesn't exceed .
 
 
 

For each test, You don't need to output the whole sequence of . Instead, you should output a non-negative integer is the result of .

2
5
1 3 1 4
5 2 0 170
1
0 0 0 1
1000000000 1000000006 1000000006 1000000007

26717147
10000019

The first test corresponds to the example in the statement.