IN C++

Chef is playing a game with two sequences of non-negative integers A1,A2,,AN and B1,B2,,BM He has an integer V, which is initially equal to 0. Chef will play for a number of turns he chooses (possibly zero); he stops playing when he gets bored. In each turn of the game, Chef must perform one of the following operations:

• Choose an integer X from A and change V to VX i.e. the bitwise OR of V and X
• Choose an integer X from B and change V to VX, i.e. the bitwise AND of V and X

Find the number of possible distinct values which V can have after the game ends.

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two space-separated integers N and M.
• The second line contains N space-separated integers A1,A2,,AN
• The third line contains M space-separated integers B1,B2,,BM

Output

For each test case, print a single line containing one integer the number of possible values of V after the game ends.

Constraints

• 1N,M2^20
• 0Ai<2^20 for each valid i
• 0Bi<2^20 for each valid i
• A1,A2,,AN are pairwise distinct
• B1,B2,,BM are pairwise distinct
• the sum of N over all test cases does not exceed 2^20
• the sum of M over all test cases does not exceed 2^20

Subtasks

Subtask #1 (30 points, time limit 2 seconds):

• 1N,M2^10
• 0Ai<2^10 for each valid i
• 0Bi<2^10 for each valid i

Subtask #2 (30 points, time limit 2 seconds):

• 1N,M2^15
• 0Ai<2^15 for each valid i
• 0Bi<2^15 for each valid i

Subtask #3 (40 points, time limit 5 seconds): original constraints

Example Input

3 3 1 5 12 14 15 6 1 0 1 3 6 12 14 1 4 3 1 3 5 6 3 6 10 

Example Output

6 9 8 

Explanation

Example case 1: V can reach the values {0,5,12,13,14,15}

Example case 2: V can reach the values {0,1,3,6,7,12,13,14,15}

Example case 3: V can reach the values {0,1,2,3,4,5,6,7}