is binary number a multiple of 3?

//https://www.geeksforgeeks.org/check-binary-string-multiple-3-using-dfa/
#include<iostream>
#include<bits/stdc++.h>
#include <stdio.h>

int main() {
	int t;
	scanf("%d", &t);
	while(t){
	    char s[100];
	    scanf("%s", &s);
        long long l = strlen(s);
        long long i = l-1, odds = 0, evens = 0, oe = -1;
	    while(i >= 0){
	        if(oe == -1){
	            if(s[i] == '1'){
	                odds++;
	            }
	        }
	        else{
	            if(s[i] == '1'){
	                evens++;
	            }
	        }
	        i--;
	        oe = oe*-1;
	    }
	    if(abs(evens-odds)%3 == 0){
	        printf("%d\n", 1);
	    }
	    else{
	        printf("%d\n", 0);
	    }
	    t--;
	}
	return 0;
}