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.