CF2228A Marisa Steals Reimu's Takeout

The Darkness Brought In by Swallowstone Naturalis Historia — Dateless Bar "Old Adam"

Marisa is a girl of integrity who always helps others safeguard their belongings. Over a period of $ n $ days, she comes each day to take one of Reimu's takeouts. The $ i $ -th takeout is described by its deliciousness value — an integer $ w_i $ ( $ 0\le w_i\le 2 $ ), forming a sequence $ w $ of length $ n $ . Marisa has a special fondness for the number $ 3 $ . She can perform the following operation zero or more times: - Select a non-empty subsequence $ ^{\text{∗}} $ of $ w $ whose sum is divisible by $ 3 $ , and remove the elements of the subsequence from $ w $ . Determine the maximum number of operations Marisa can perform. $ ^{\text{∗}} $ A sequence $ a $ is a subsequence of a sequence $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1\le n \le 100 $ ). The second line contains $ n $ integers $ w_1, w_2, \ldots, w_n $ ( $ 0\leq w_i \leq 2 $ ), denoting the deliciousness values of the takeouts.

For each test case, output the maximum number of operations Marisa can perform.

In the first test case, Marisa can perform four operations: $ [\underline{0},0,0,0]\to[\underline{0},0,0]\to[\underline{0},0]\to[\underline{0}]\to []. $ In the second test case, Marisa can perform two operations: $ [\underline{1},\underline{2},0]- \gt [\underline{0}]- \gt []. $ In the third test case, Marisa can perform two operations: $ [\underline{1},2,1,\underline{2},1]- \gt [\underline{2},1,\underline{1}]- \gt [1]. $