This page is still under construction.

Parts of this page are still being built. What you see may change.

Hello 2020 Hello 2021

Time limit1.5sMemory limit512 MB

Summary
Count pairs whose sum has first four digits 2020 and last four digits 2021, among n integers.
Level

Medium7 of 10

Topics
Hash map, Math, Implementation, Combinatorics
Solved
No attempts yet

Problem

To mark the end of 2020 and the start of 2021, Albert decided to solve an interesting problem. A positive integer is called a happy integer if its first four digits are "2020" and its last four digits are "2021". For example, 202021 and 20202021 are happy integers, while 2020021 and 2020221 are not.

Albert wants to know the number of pairs among n integers A[1], A[2], ..., A[n] whose sum is a happy integer. In other words, he wants the number of pairs (i, j) with 1 ≤ i < j ≤ n such that A[i] + A[j] is a happy integer. For example, let A = [101010, 101010, 101011, 101011], so n = 4. Here A[1] + A[3] = A[1] + A[4] = A[2] + A[3] = A[2] + A[4] = 202021, so there are 4 such pairs: (1, 3), (1, 4), (2, 3), (2, 4).

Given n integers as input, output the number of pairs whose sum is a happy integer.

Input

The first line contains the number of test cases T. Each test case consists of two lines.

The first line contains the number of integers n. The next line contains n integers separated by spaces.

Output

For each test case, output the number of pairs whose sum is a happy integer.

Constraints

  • 1 ≤ T ≤ 10
  • 2 ≤ n ≤ 100,000
  • -228 ≤ A[i] ≤ 228

Examples1

  1. Example 1

    Input
    3
4
101010 101010 101011 101011
5
100000 100000 100000 101011 101011
4
202021 0 1 202020
    Expected output
    4
0
2