import sys
from collections import defaultdict
# Constants
MOD = int ( 1e9 + 7 )
# Game state tracking
game_grid = [ ]
state_map = defaultdict( int )
column_depth = [ 0 ] * 7 # Track the fill depth of each column
# Check for a 4-in-a-row pattern starting from a specific cell
def check_sequence( start_row, start_col, row_step, col_step, player) :
for i in range ( 4 ) :
row = start_row + i * row_step
col = start_col + i * col_step
if column_depth[ col] > row or game_grid[ row] [ col] != player:
return False
return True
# Count the number of "4-in-a-row" sequences for both players ('F' and 'C')
def count_sequences( ) :
rows = len ( game_grid)
cols = len ( game_grid[ 0 ] )
player_f_count = 0
player_c_count = 0
for row in range ( rows) :
for col in range ( cols) :
if col + 3 < cols: # Horizontal
player_f_count += check_sequence( row, col, 0 , 1 , 'F' )
player_c_count += check_sequence( row, col, 0 , 1 , 'C' )
if row + 3 < rows: # Vertical
player_f_count += check_sequence( row, col, 1 , 0 , 'F' )
player_c_count += check_sequence( row, col, 1 , 0 , 'C' )
if row + 3 < rows and col + 3 < cols: # Diagonal down-right
player_f_count += check_sequence( row, col, 1 , 1 , 'F' )
player_c_count += check_sequence( row, col, 1 , 1 , 'C' )
if row + 3 < rows and col - 3 >= 0 : # Diagonal down-left
player_f_count += check_sequence( row, col, 1 , -1 , 'F' )
player_c_count += check_sequence( row, col, 1 , -1 , 'C' )
# Stop counting early if both players have sequences
if player_f_count > 0 and player_c_count > 0 :
return player_f_count, player_c_count
return player_f_count, player_c_count
# Recursive function to simulate the game and determine the result
def simulate_game( turn) :
game_state = '' .join ( map ( str , column_depth) )
if game_state in state_map:
return state_map[ game_state]
f_seq, c_seq = count_sequences( )
if f_seq == 0 and c_seq == 0 :
state_map[ game_state] = 0
elif f_seq > 0 and c_seq == 0 :
state_map[ game_state] = 1
elif f_seq == 0 and c_seq > 0 :
state_map[ game_state] = -1
else :
current_player = 'F' if turn == 1 else 'C'
result = 0
for col in range ( 7 ) :
if column_depth[ col] < len ( game_grid) and game_grid[ column_depth[ col] ] [ col] == current_player:
column_depth[ col] += 1
opponent_result = simulate_game( 1 - turn)
column_depth[ col] -= 1
if opponent_result == 0 :
continue
elif opponent_result == 1 :
result = max ( result, 1 )
elif opponent_result == -1 :
result = min ( result, -1 )
state_map[ game_state] = result
return state_map[ game_state]
# Handle input and process each test case
def process_case( ) :
global game_grid, column_depth, state_map
state_map.clear ( )
column_depth = [ 0 ] * 7 # Reset column depths
game_grid = [ input ( ) .strip ( ) for _ in range ( 6 ) ] # Read the 6x7 grid
return simulate_game( 1 )
# Main function to drive the program
if __name__ == "__main__" :
input = sys .stdin .read
data = input ( ) .splitlines ( )
test_cases = int ( data[ 0 ] )
index = 1
for case_num in range ( 1 , test_cases + 1 ) :
game_grid = data[ index:index + 6 ]
index += 6
print ( f"Case #{case_num}: " , end= "" )
result = process_case( )
if result == 1 :
print ( "F" )
elif result == -1 :
print ( "C" )
elif result == 0 :
print ( "0" )
else :
print ( "?" )
aW1wb3J0IHN5cwpmcm9tIGNvbGxlY3Rpb25zIGltcG9ydCBkZWZhdWx0ZGljdAoKIyBDb25zdGFudHMKTU9EID0gaW50KDFlOSArIDcpCgojIEdhbWUgc3RhdGUgdHJhY2tpbmcKZ2FtZV9ncmlkID0gW10Kc3RhdGVfbWFwID0gZGVmYXVsdGRpY3QoaW50KQpjb2x1bW5fZGVwdGggPSBbMF0gKiA3ICAjIFRyYWNrIHRoZSBmaWxsIGRlcHRoIG9mIGVhY2ggY29sdW1uCgojIENoZWNrIGZvciBhIDQtaW4tYS1yb3cgcGF0dGVybiBzdGFydGluZyBmcm9tIGEgc3BlY2lmaWMgY2VsbApkZWYgY2hlY2tfc2VxdWVuY2Uoc3RhcnRfcm93LCBzdGFydF9jb2wsIHJvd19zdGVwLCBjb2xfc3RlcCwgcGxheWVyKToKICAgIGZvciBpIGluIHJhbmdlKDQpOgogICAgICAgIHJvdyA9IHN0YXJ0X3JvdyArIGkgKiByb3dfc3RlcAogICAgICAgIGNvbCA9IHN0YXJ0X2NvbCArIGkgKiBjb2xfc3RlcAogICAgICAgIGlmIGNvbHVtbl9kZXB0aFtjb2xdID4gcm93IG9yIGdhbWVfZ3JpZFtyb3ddW2NvbF0gIT0gcGxheWVyOgogICAgICAgICAgICByZXR1cm4gRmFsc2UKICAgIHJldHVybiBUcnVlCgojIENvdW50IHRoZSBudW1iZXIgb2YgIjQtaW4tYS1yb3ciIHNlcXVlbmNlcyBmb3IgYm90aCBwbGF5ZXJzICgnRicgYW5kICdDJykKZGVmIGNvdW50X3NlcXVlbmNlcygpOgogICAgcm93cyA9IGxlbihnYW1lX2dyaWQpCiAgICBjb2xzID0gbGVuKGdhbWVfZ3JpZFswXSkKICAgIHBsYXllcl9mX2NvdW50ID0gMAogICAgcGxheWVyX2NfY291bnQgPSAwCgogICAgZm9yIHJvdyBpbiByYW5nZShyb3dzKToKICAgICAgICBmb3IgY29sIGluIHJhbmdlKGNvbHMpOgogICAgICAgICAgICBpZiBjb2wgKyAzIDwgY29sczogICMgSG9yaXpvbnRhbAogICAgICAgICAgICAgICAgcGxheWVyX2ZfY291bnQgKz0gY2hlY2tfc2VxdWVuY2Uocm93LCBjb2wsIDAsIDEsICdGJykKICAgICAgICAgICAgICAgIHBsYXllcl9jX2NvdW50ICs9IGNoZWNrX3NlcXVlbmNlKHJvdywgY29sLCAwLCAxLCAnQycpCiAgICAgICAgICAgIGlmIHJvdyArIDMgPCByb3dzOiAgIyBWZXJ0aWNhbAogICAgICAgICAgICAgICAgcGxheWVyX2ZfY291bnQgKz0gY2hlY2tfc2VxdWVuY2Uocm93LCBjb2wsIDEsIDAsICdGJykKICAgICAgICAgICAgICAgIHBsYXllcl9jX2NvdW50ICs9IGNoZWNrX3NlcXVlbmNlKHJvdywgY29sLCAxLCAwLCAnQycpCiAgICAgICAgICAgIGlmIHJvdyArIDMgPCByb3dzIGFuZCBjb2wgKyAzIDwgY29sczogICMgRGlhZ29uYWwgZG93bi1yaWdodAogICAgICAgICAgICAgICAgcGxheWVyX2ZfY291bnQgKz0gY2hlY2tfc2VxdWVuY2Uocm93LCBjb2wsIDEsIDEsICdGJykKICAgICAgICAgICAgICAgIHBsYXllcl9jX2NvdW50ICs9IGNoZWNrX3NlcXVlbmNlKHJvdywgY29sLCAxLCAxLCAnQycpCiAgICAgICAgICAgIGlmIHJvdyArIDMgPCByb3dzIGFuZCBjb2wgLSAzID49IDA6ICAjIERpYWdvbmFsIGRvd24tbGVmdAogICAgICAgICAgICAgICAgcGxheWVyX2ZfY291bnQgKz0gY2hlY2tfc2VxdWVuY2Uocm93LCBjb2wsIDEsIC0xLCAnRicpCiAgICAgICAgICAgICAgICBwbGF5ZXJfY19jb3VudCArPSBjaGVja19zZXF1ZW5jZShyb3csIGNvbCwgMSwgLTEsICdDJykKCiAgICAgICAgICAgICMgU3RvcCBjb3VudGluZyBlYXJseSBpZiBib3RoIHBsYXllcnMgaGF2ZSBzZXF1ZW5jZXMKICAgICAgICAgICAgaWYgcGxheWVyX2ZfY291bnQgPiAwIGFuZCBwbGF5ZXJfY19jb3VudCA+IDA6CiAgICAgICAgICAgICAgICByZXR1cm4gcGxheWVyX2ZfY291bnQsIHBsYXllcl9jX2NvdW50CiAgICByZXR1cm4gcGxheWVyX2ZfY291bnQsIHBsYXllcl9jX2NvdW50CgojIFJlY3Vyc2l2ZSBmdW5jdGlvbiB0byBzaW11bGF0ZSB0aGUgZ2FtZSBhbmQgZGV0ZXJtaW5lIHRoZSByZXN1bHQKZGVmIHNpbXVsYXRlX2dhbWUodHVybik6CiAgICBnYW1lX3N0YXRlID0gJycuam9pbihtYXAoc3RyLCBjb2x1bW5fZGVwdGgpKQogICAgCiAgICBpZiBnYW1lX3N0YXRlIGluIHN0YXRlX21hcDoKICAgICAgICByZXR1cm4gc3RhdGVfbWFwW2dhbWVfc3RhdGVdCgogICAgZl9zZXEsIGNfc2VxID0gY291bnRfc2VxdWVuY2VzKCkKICAgIAogICAgaWYgZl9zZXEgPT0gMCBhbmQgY19zZXEgPT0gMDoKICAgICAgICBzdGF0ZV9tYXBbZ2FtZV9zdGF0ZV0gPSAwCiAgICBlbGlmIGZfc2VxID4gMCBhbmQgY19zZXEgPT0gMDoKICAgICAgICBzdGF0ZV9tYXBbZ2FtZV9zdGF0ZV0gPSAxCiAgICBlbGlmIGZfc2VxID09IDAgYW5kIGNfc2VxID4gMDoKICAgICAgICBzdGF0ZV9tYXBbZ2FtZV9zdGF0ZV0gPSAtMQogICAgZWxzZToKICAgICAgICBjdXJyZW50X3BsYXllciA9ICdGJyBpZiB0dXJuID09IDEgZWxzZSAnQycKICAgICAgICByZXN1bHQgPSAwCgogICAgICAgIGZvciBjb2wgaW4gcmFuZ2UoNyk6CiAgICAgICAgICAgIGlmIGNvbHVtbl9kZXB0aFtjb2xdIDwgbGVuKGdhbWVfZ3JpZCkgYW5kIGdhbWVfZ3JpZFtjb2x1bW5fZGVwdGhbY29sXV1bY29sXSA9PSBjdXJyZW50X3BsYXllcjoKICAgICAgICAgICAgICAgIGNvbHVtbl9kZXB0aFtjb2xdICs9IDEKICAgICAgICAgICAgICAgIG9wcG9uZW50X3Jlc3VsdCA9IHNpbXVsYXRlX2dhbWUoMSAtIHR1cm4pCiAgICAgICAgICAgICAgICBjb2x1bW5fZGVwdGhbY29sXSAtPSAxCiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIGlmIG9wcG9uZW50X3Jlc3VsdCA9PSAwOgogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICBlbGlmIG9wcG9uZW50X3Jlc3VsdCA9PSAxOgogICAgICAgICAgICAgICAgICAgIHJlc3VsdCA9IG1heChyZXN1bHQsIDEpCiAgICAgICAgICAgICAgICBlbGlmIG9wcG9uZW50X3Jlc3VsdCA9PSAtMToKICAgICAgICAgICAgICAgICAgICByZXN1bHQgPSBtaW4ocmVzdWx0LCAtMSkKCiAgICAgICAgc3RhdGVfbWFwW2dhbWVfc3RhdGVdID0gcmVzdWx0CiAgICByZXR1cm4gc3RhdGVfbWFwW2dhbWVfc3RhdGVdCgojIEhhbmRsZSBpbnB1dCBhbmQgcHJvY2VzcyBlYWNoIHRlc3QgY2FzZQpkZWYgcHJvY2Vzc19jYXNlKCk6CiAgICBnbG9iYWwgZ2FtZV9ncmlkLCBjb2x1bW5fZGVwdGgsIHN0YXRlX21hcAogICAgc3RhdGVfbWFwLmNsZWFyKCkKICAgIGNvbHVtbl9kZXB0aCA9IFswXSAqIDcgICMgUmVzZXQgY29sdW1uIGRlcHRocwogICAgZ2FtZV9ncmlkID0gW2lucHV0KCkuc3RyaXAoKSBmb3IgXyBpbiByYW5nZSg2KV0gICMgUmVhZCB0aGUgNng3IGdyaWQKICAgIHJldHVybiBzaW11bGF0ZV9nYW1lKDEpCgojIE1haW4gZnVuY3Rpb24gdG8gZHJpdmUgdGhlIHByb2dyYW0KaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIGlucHV0ID0gc3lzLnN0ZGluLnJlYWQKICAgIGRhdGEgPSBpbnB1dCgpLnNwbGl0bGluZXMoKQoKICAgIHRlc3RfY2FzZXMgPSBpbnQoZGF0YVswXSkKICAgIGluZGV4ID0gMQoKICAgIGZvciBjYXNlX251bSBpbiByYW5nZSgxLCB0ZXN0X2Nhc2VzICsgMSk6CiAgICAgICAgZ2FtZV9ncmlkID0gZGF0YVtpbmRleDppbmRleCArIDZdCiAgICAgICAgaW5kZXggKz0gNgoKICAgICAgICBwcmludChmIkNhc2UgI3tjYXNlX251bX06ICIsIGVuZD0iIikKICAgICAgICByZXN1bHQgPSBwcm9jZXNzX2Nhc2UoKQoKICAgICAgICBpZiByZXN1bHQgPT0gMToKICAgICAgICAgICAgcHJpbnQoIkYiKQogICAgICAgIGVsaWYgcmVzdWx0ID09IC0xOgogICAgICAgICAgICBwcmludCgiQyIpCiAgICAgICAgZWxpZiByZXN1bHQgPT0gMDoKICAgICAgICAgICAgcHJpbnQoIjAiKQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHByaW50KCI/IikK