首先说一个概念，任意自然数N，其各位数字相加之和为M，那么N与M对模3同余。根据同余定理，可以先对N的每一位数字除以3取余，再相加后除以3取余，结果依然和N直接除以3取余相同。

举个例子1234567除以3余1，1+2+3+4+5+6+7 = 28除以3余1。分别对计算1-7除以3的余数再相加，得到1+2+0+1+2+0+1 = 7除以3余1。

这里的数学原理其实很简单，我们令个位数字是第0位，十位数字是第1位，百位数字是第2位，以此类推。假设自然数N的第i位数字是n，那么这位数字n实际代表的数是n乘以10的i次方。注意到10的i次方减去1得到999...99（i个9）必然被3整除，因此10^i 除以3必然余数是1。那么n * 10^i 与n对模3同余。相信聪明的小伙伴已经发现了，把模3改成模9，可以得到相同的结论。

好了，数学原理分析到这里，接下来开始解题。首先创建一个数组vMod，vMod[i]表示原数各位数字中除以3余数为i的个数。那么(vMod[1] + vMod[2] * 2) % 3就是原数除以3的余数，记为m。接下来具体问题具体分析。

【1】若m为0，即原数为3的倍数，那么依次去掉数字0，3，6，9这些3的倍数的数字即可，ans = vMod[0]。这里注意边界条件，若全部数字都是3的倍数，那么当剩下最后一个数字时就不能再去掉了，答案修正为ans - 1。

【2】若m不为0，即原数不是3的倍数，此时m只能是1或2。那么第一步我们需要去掉某个数，使得剩下的数满足%3 == 0的条件，接下来再依次去掉数字0，3，6，9这些3的倍数的数字即可，ans = vMod[0] + 1。注意！！！这里去掉的某个数可能并不存在，此时ans = 0。判断的依据就是vMod[m]的值是否大于0。举个例子119999，这里的m = 2，vMod[2] = 0，因此答案为0。

然后我们再分析【2】的边界条件。这里就比较恶心了，有2个边界条件。第一个条件和【1】中类似，若最后ans等于原数各位数字的个数，那么当剩下最后一个数字时就不能再去掉了，答案修正为ans - 1；第二个条件，若vMod[m] = 1，且对应的数字正好是原数的最高位数字，就要考虑前导0的情况。举例2001497，这里m = 2，第一次去除数字只能去除最高位2，此时该数字就变成了1497，还能再删除9，最终ans = 2。观察发现vMod[0] + 1 = 4，和ans正好相差2，这个数字正好是最高位去掉后前导0的个数。因此这种情况下ans = vMod[0] + 1 - 最高位后前导零个数。

好了，大功告成，提交~

结果……没有AC。

原因是，当【2】的两个边界条件结合起来时，情况又会发生变化。举例数字10003，根据公式前导零个数为3，因此ans = vMod[0] + 1 - 3 = 2。实际情况是，ans = 1，当首位的1去除后，剩下数字是3，不能再去除了。类似的数字2000，使用公式计算ans = 1，而实际ans = 0。

找到问题后就简单了，首先ans = vMod[0] + 1，判断ans的值是否等于原数各位数字的个数，若是则修正ans = ans - 1。接下来再判断vMod[m] = 1，且对应的数字正好是原数的最高位数字的情况，ans = ans - 最高位后前导零个数。

下面贴出代码。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    string n;
    while (t--) {
        cin >> n;
        vector<int> vMod(3, 0);//vMod[i]表示原数各位数字中除以3余数为i的个数
        for (char& c : n) {
            ++vMod[(c - '0') % 3];
        }
        int m = (vMod[1] + vMod[2] + vMod[2]) % 3; //原数除以3的余数
        int ans;
        if (m == 0) { //原数为3的倍数
            ans = vMod[0];
            if (ans == n.size()) --ans;
        } else { //原数不是3的倍数
            if (vMod[m] == 0) {   //没有任何一位数字跟原数模3同余
                ans = 0;
            } else {
                ans = vMod[0] + 1; //先删掉同余数字，再删余数为0的
                if (ans == n.size()) --ans;
                if (vMod[m] == 1 && (n[0] - '0') % 3 == m) {
                    for (int i = 1; i < n.size(); ++i) {
                        if (n[i] != '0') break;
                        --ans;
                    }
                }
            }
        }
        cout << ans << endl;
    }
}