Engineering of the Clones

Problem Description

Cloning was the process of creating a genetically identical or¡ªpurposefully and specifically¡ªmodified copy of an original organism. It was also one of the key factors that facilitated the end of the Galactic Republic and the dawn of the Galactic Empire in its place. Through the science of cloning, a vast clone army was created on Kamino for the purpose of serving the Republic. Programmed with absolute loyalty to Supreme Chancellor Palpatine, leader of the Galactic Senate and secretly the Sith Lord Darth Sidious, the clones proved to be instrumental in his rise to the position of Emperor. The military applications of cloning were further exploited by the New Order through the creation of countless more clone soldiers, all used mainly for the sole purpose of spreading and enforcing Imperial hegemony throughout the galaxy.

¡ª Wookieepedia The clones are engineered such that all have exactly the same genetic footprint, and are flash-learned directly from a template. Thus, all clones should be completely identical to the original person in theory. However, the cloning procedure is proven to be defective. A clone may be physically deformed and will die in his early age, or even worse, a seemingly functional clone may also have tiny defects in the brain development that may leak secretly programmed information. During the Clone War, such a rare case was reported: a Jedi was killed by a malfunctioning clone believed that the Order 66 has been issued, and the case nearly lead to the Jedi Council to discover the secret plan of the evil Darth Sidious. After the malfunctioning case was reported, Chancellor Palpatine decided to carefully test all clones before they are being delivered to the battlefield. This is done by a procedure called "high-precision genome fingerprinting" that balances the time and the money. In particular, the entire gnome of a clone is taken and encoded as a single number. Only one digit of that number is actually sampled and tested. Given genes denoted by prime numbers $p_1, p_2, .. , p_n$, the genome of the clone is represented by a number $A$ defined as

$$A=p_1^{r_1} p_2^{r_2} .. p_n^{r_n}$$

where

$$\left| r_i - r_j \right| \le 1, 1 \le i \le j \le n. $$

Since $A$ may be huge in size, the test process only samples one digit as the fingerprint: the $k$-th digit of $\frac{1}{A - 1}$ written in base $\prod_{i=1}^{n} p_i$. You received the mission of designing an algorithm to perform the genome fingerprinting test. Given a genome description ($p_i$ and $r_i$) and $k$, you should find the fingerprint value.

Input

The first line of the input contains an integer $T$, denoting the number of test cases. For each test case, the first line contains two integers $n$ ($1\le n\le 10^6$) and $k$ ($1\le k \lt \max\{r^2_1, r^2_2, .. , r^2_n\}$). The next line contains $n$ distinct primes. The $i$-th number is $p_i$ $1\le \prod_{i=1}^{n} p_i \le 10^6$. The next line contains $n$ integers. The $i$-th number is $r_i$ ($1\le r_i \le 5 * 10^4$).

Output

You should output the answers for the queries, one integer per line.

Sample Input

1

2 1

2 5

2 2

Sample Output

0

Source

2017 Multi-University Training Contest - Team 8

https://acm.hdu.edu.cn/showproblem.php?pid=6137