You are given an integer n and two arrays each of which is a permutation of numbers from $1$ to n. 

Task

Your task is to determine the number of unordered triplets $(a,b,c)$ such that the relative ordering of $(a,b,c)$ is the same in both the arrays.

Example

Assumptions

• A = [4, 1, 3, 2]
• B = [1, 4, 3, 2] 

Approach

There exist two unordered triplets such that the relative ordering of triplet is same in both the permutation arrays:

• (4, 3, 2) and (1, 3, 2) are the required triplets

Function description

Complete the countTriplet function provided in the editor. The function takes the following 3 parameters and returns the number of ordered triplets.

• n: Represents the length of the permutation
• A: Represents the first permutation of numbers from 1 to n
• B: Represents the second permutation of numbers from 1 to n

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains an integer T denoting the number of test cases. T also denotes the number of times you have to run the countTriplet function on a different set of inputs.
• For each test case:
  • The first line contains a single integer n. 
  • Each of the next two lines contains n space-separated integers denoting the permutations of numbers from 1 to n.

Output format

For each test case, print the number of ordered triplets in a new line

Constraints
$1 \le T \le 100$
$1 \le n \le 100000$

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.