Johnny is a gambling addict. He entered a casino and started playing a game with the dealer. The game is as follows: the dealer deals a sequence of N cards, each card containing a number C[i] and asks Johnny how many pairs (j, k) such that j < k and C[j] + C[k] = X. If Johnny answers correctly he wins, otherwise the dealer wins.

Input

The first line of input contains an integer T, the number of test cases. T test cases follow, Each test case start with the value of 0 ≤ X ≤ 2*10³ followed by the number of cards 0 < N ≤ 10⁵ followed by N numbers representing the numbers on the cards 0 ≤ C[i] ≤ 10³.

Output

There should be T lines, containing the following format.

k. S

Where k is the test case number (starting at 1), a single period, a single space and S representing the number of valid pairs (j, k) as described above.

Sample

Input
1
10 3 1 5 9

Output
1. 1