<?php
$ip = fopen('php://stdin', "r"); $op = fopen('php://stdout',"w"); $c = 0;
while($c < $test_cases){
$turn = 1;
while($case>2){
$limit = $case/2;
$a=2;
while(($a < $limit)){
$factor = $case/$a;
if(floor($factor) == $factor){ break;
}else{
$factor = 1;
}
$a++;
}
$case = $case - $factor;
$turn++;
}
while($case>1){
$case--;
$turn++;
}
if(($turn % 2) == 0){
}else{
}
$c++;
}
?>
PD9waHAKCiRpcCA9IGZvcGVuKCdwaHA6Ly9zdGRpbicsICJyIik7CiRvcCA9IGZvcGVuKCdwaHA6Ly9zdGRvdXQnLCJ3Iik7CiR0ZXN0X2Nhc2VzID0gdHJpbShmZ2V0cygkaXApKTsKJGMgPSAwOwoKd2hpbGUoJGMgPCAkdGVzdF9jYXNlcyl7CgkkdHVybiA9IDE7CgkkY2FzZSA9IHRyaW0oZmdldHMoJGlwKSk7Cgl3aGlsZSgkY2FzZT4yKXsKCQkkbGltaXQgPSAkY2FzZS8yOwoJCSRhPTI7CgkJd2hpbGUoKCRhIDwgJGxpbWl0KSl7CgkJCSRmYWN0b3IgPSAkY2FzZS8kYTsKCQkJaWYoZmxvb3IoJGZhY3RvcikgPT0gJGZhY3Rvcil7CgkJCQlicmVhazsKCQkJfWVsc2V7CgkJCQkkZmFjdG9yID0gMTsKCQkJfQoJCQkkYSsrOwoJCX0KCQkkY2FzZSA9ICRjYXNlIC0gJGZhY3RvcjsKCQkkdHVybisrOwoJfQoJd2hpbGUoJGNhc2U+MSl7CgkJJGNhc2UtLTsKCQkkdHVybisrOwoJfQoJaWYoKCR0dXJuICUgMikgPT0gMCl7CgkJZndyaXRlKCRvcCwgc3ByaW50ZigiJXNcbiIsIkFMSUNFIikpOwoJfWVsc2V7CgkJZndyaXRlKCRvcCwgc3ByaW50ZigiJXNcbiIsIkJPQiIpKTsKCX0JCgoJJGMrKzsKfQo/Pgo=