F. Атака на Красное Королевство
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Красное Королевство атаковано войсками Белого Короля и Черного Короля!

Королевство охраняют $$$n$$$ замков, $$$i$$$-й из которых защищают $$$a_i$$$ солдат. Чтобы захватить Королевство, необходимо уничтожить всех солдат, защищающих замки.

Каждый день Белый Король атакует один из замков. Затем ночью войска Черного Короля атакуют один из замков (возможно, тот же самый). После этого снова следует атака Белого Короля, потом атака Черного Короля, и так далее. Первую атаку проводит Белый Король.

Целью каждой атаки должен быть замок с хотя бы одним живым защитником. Существует три типа атак:

  • смешанная атака уменьшает количество защитников замка на $$$x$$$ (или до $$$0$$$, если их было меньше $$$x$$$);
  • атака пехоты уменьшает количество защитников замка на $$$y$$$ (или до $$$0$$$, если их было меньше $$$y$$$);
  • атака конницы уменьшает количество защитников замка на $$$z$$$ (или до $$$0$$$, если их было меньше $$$z$$$).

Смешанная атака может быть проведена по любой цели (по любому замку, в котором жив хотя бы один защитник). Однако атака пехоты не может быть проведена по замку, если предыдущая атака на этот замок была того же самого типа, вне зависимости от того, кто и когда провел эту атаку. То же самое относится к атаке конницы. Еще не атакованный замок доступен как цель для атаки любого типа.

Король, который проведет последнюю атаку, будет прославлен как завоеватель Красного Королевства, поэтому оба Короля хотят провести последнюю атаку (и они достаточно мудры, чтобы составить план действий, который позволит им это сделать вне зависимости от действий оппонента, если это возможно). Войска Белого Короля готовятся к первой атаке, а вам поручено ее распланировать. Сможете ли вы посчитать количество возможных вариантов первой атаки, при которых у Белого Короля есть стратегия, позволяющая ему провести последнюю атаку вне зависимости от действий Черного Короля? Каждый вариант первой атаки — это тип атаки и номер атакуемого замка, и два варианта различны, если хоть что-то из этого отличается в этих вариантах.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Затем следуют сами входные данные. Каждый набор входных данных состоит из двух строк.

В первой строке заданы четыре целых числа $$$n$$$, $$$x$$$, $$$y$$$ и $$$z$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le x, y, z \le 5$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^{18}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора тестовых данных выведите ответ на него — одно целое число, равное количеству возможных вариантов для первой атаки (или $$$0$$$, если у Черного Короля всегда будет возможность провести последнюю атаку, вне зависимости от действий Белого Короля).

Примеры
Входные данные
3
2 1 3 4
7 6
1 1 2 3
1
1 1 2 2
3
Выходные данные
2
3
0
Входные данные
10
6 5 4 5
2 3 2 3 1 3
1 5 2 3
10
4 4 2 3
8 10 8 5
2 2 1 4
8 5
3 5 3 5
9 2 10
4 5 5 5
2 10 4 2
2 3 1 4
1 10
3 1 5 3
9 8 7
2 5 4 5
8 8
3 5 1 4
5 5 10
Выходные данные
0
2
1
2
5
12
5
0
0
2