Alyona and a Square Jigsaw Puzzle

// Problem Link - 
/* Created By: 
 *   Ujjwal Bharti
 */
/*   ⠀⢀⣴⣶⣶⣆⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⣴⣤⣶⣶⣶⣶⣦⣶⣾⣿⣿⣷⣾⣿⣿⣿⣿⣶⡦⣀⠀⠀⠀⣠⠤⣤⡆
⠀⠀⠀⠀⠀⠀⣿⡆⣠⣿⣿⣿⡏⣿⣴⣿⣿⣿⣶⣆⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⣸⣁⣀⣿
⠀⠀⠀⠀⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⢻⣿⣯⢿⣿⣿⣧⡙⣾⣿
⠀⠀⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟
⠀⢀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣷
⠀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣀⡄
⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣤⣤⠀⠀⠀⠀⠀⠀⠀
⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡁⠂⠀⠀⠀⠀⠀⠀⠀
⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣿⣷⣆⡀⠀⠀⠀
⠀⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢦⡀⠀
⠀⠀⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡁⠀
⠀⠀⠀⠘⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⠻⠟⡛⠛⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⠿⢋⠛⠉⠀⠘⠇⠀⠀⠀⠀⡼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⢙⡾⢭⣽⣿⣿⡿⠿⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⡼⠒⠋⠉⠉⠁⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢁⡹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡾⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣄⣷⣌⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠂⠀⠀⠀⠐⠀⠀⠐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣸⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀
⠀⠀⠀⠀⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠂⠀⠀⠀⠐⠀⠀⠀⠀⠀⠐⠦⢐⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀
⠀⠀⠀⢠⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠙⠛⠙⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀
⠀⠀⢠⣾⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⢀⣠⣤⣴⣾⣿⣷⣶⣦⣤⣤⣀⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀
⠀⠀⠸⣿⣿⣧⡄⠀⠀⠀⠀⠀⢀⣠⣶⣾⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⠻⠿⣿⣿⣶⡄⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠛⢿⣿⣿⡟⠀⠀⠀
⠀⠀⠀⠻⣿⣿⣿⣶⣤⣄⢢⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⣤⡀⠀⠀⠀⠀⠘⠛⠷⢀⠀⠀⠀⠀⠀⠀⠁⣺⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⢁⡴⠋⠉⠙⢧⡙⣿⡇⠀⠀⠀
⠀⠀⠀⠶⡿⣿⢻⣿⣿⣿⡖⠸⣿⡿⠛⣣⣖⣿⣿⣿⢿⣿⣿⣿⣿⣿⣦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⣿⣿⣿⣿⣿⣿⡿⠃⠀⣰⡿⠀⠀⠀⠀⣀⣷⢸⠇⠀⠀⠀
⠀⠀⠀⠀⢠⣾⣦⣿⣿⣿⠃⠀⠹⣷⣾⣿⣿⣿⣿⣁⠀⠘⣿⣿⣿⣿⣿⣿⣷⣄⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡿⣿⣿⣿⣿⡟⢀⠀⢀⣿⣷⣷⠟⠙⠻⠿⠛⣸⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢻⣿⢿⣿⠏⠀⠀⠀⠙⣿⣿⣿⣿⣿⡋⠉⠋⠋⠉⠉⣻⣿⠏⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡧⣿⣿⣿⣿⡏⠹⣷⢸⣿⣿⣧⠀⠀⡀⠀⢰⡟⠀⠀⠀⠀
⠀⠀⠀⠀⠀⡞⣻⣿⠏⠀⠀⠀⠀⠀⠈⠙⠿⢿⣿⣿⣷⣤⣄⣴⣾⣿⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⠋⠀⠀⣿⠈⢟⣾⠿⠋⢠⣷⢀⡿⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢸⡇⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⣿⢋⠛⠋⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⣿⣿⣿⣿⣿⠀⢠⣴⣿⣴⠟⠁⠀⣠⣾⠋⣼⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢸⣿⠏⠀⠀⠀⠀⠀⠀⠄⠀⢠⣤⡀⠀⠀⠈⠀⠀⠐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⣿⣿⣿⣿⣿⣷⠀⣾⠿⠟⢀⣠⣤⠾⠟⢁⣾⣿⠁⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠈⣯⡀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢏⡷⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠀⣸⣿⣿⣿⣿⡷⢸⠛⠀⣴⢿⣿⡇⠀⣰⣿⣿⡯⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠘⣿⣌⢻⣿⣷⣶⣦⣄⠀⠀⢸⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⠀⡀⠀⠀⣾⣶⣿⣿⣿⣿⣿⡅⢸⡄⠀⠀⠀⠀⢀⣼⡿⠵⣽⣗⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢿⣹⣾⣿⣽⣿⣿⣿⣷⣾⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⣄⣿⣿⣿⣿⣿⣿⣿⣿⣼⣷⣄⣀⣠⣴⣿⣿⣧⠇⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠽⢁⣰⣿⣷⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⠩⠟⣻⢿⣿⣿⣍⢐⣿⣿⡄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣿⣿⢃⣦⡄⠀⠀⠀⠀⠈⡀⠠⠀⢀⣶⣴⣶⣾⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⣄⣡⣾⣾⣿⣿⣷⣿⣿⣿⣧⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣦⡀⠀⣀⠐⠁⠂⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣼⣦⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣦⣤⣀⡀⠀
⠀⠀⠀⠀⠀⠀⢻⣿⣷⣿⣜⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⠐⢄⣶⣻⣿⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣋⡼
⠀⠀⠀⠀⠀⠀⣼⣡⣿⢻⣿⣿⣿⣿⣿⣿⠟⠿⣿⣿⣿⣿⣿⣧⣤⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡄⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⢿⣿
⠀⠀⠀⠀⠀⠀⣿⣧⣦⣤⣤⣬⣭⡭⡉⠀⠀⠀⣽⢻⣿⣿⣿⣿⣿⣬⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣅⠇⠀⠀⠻⣿⣿⣿⣿⡽⣿⡵⣻⣷⣿⣿⡿⣞
⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣶⣿⢋⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡻⠀⠀⢠⣴⣿⢟⣽⣿⣿⣿⣾⣵⣿⣾⣿⣿⣽
⠀⠀⠀⠀⠀⠸⣿⣿⣿⣿⣿⣿⣿⡿⣻⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⣀⣴⣿⣿⣿⣿⣿⣟⣽⣫⣿⣿⣿⣿⡽⣻⡿
⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣾⣿⢿⡵⣿⣻⣿⣿⣿⣿⣿⣷⡯⣿⣿⣿⣕⣯
⠀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡷⣻⣿⣝⡿⣻⣿⣿⣿⣿⣿⣾⡿⣟⡿⢿⣻
⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣩⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡽⣻⣿⣾⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣷⣯⡶⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠉⠙⢶⡙⡣⠙⠫⣿⡸⢿⣻⣿⣿⣿⣿⣿⣿⣿⣾⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡯⣿⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠛⠛⠿⠿⠿⢿⠟⠛⠟⠙⠋⠀⠀⠀⠀⠀⠳⣄⠀⠄⠁⠐⡭⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡛⠉⠈⠙⠻⠎⢡
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣦⠄⠀⠂⢽⢭⣿⣿⣿⣿⣿⣿⣟⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⠿⠿⡻⣗⣶⣤⣤⣀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⡄⡇⠄⣀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣦⣤⣤⣶⣤
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣸⡐⣢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣛⣛⣛⣛
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣯⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣻⣿⣿⣽⣿⣿⣭⣿⣿⢯⣻⣝
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡿⣫⣿⣿⣿⠟⣻⣿⣾⣿⣷⣾⣿⣿⣿⣿⣿⣿⣟⣫⣽
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣷⣿⣿⣿⣿⣿⢟⣿⣿⣿⣿⡿⢣⣾⣟⣴⢿⠉⣿⣿⣽⣿⡿⣖⢾⢻⣽⣮⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣟⣵⣿⣯⣸⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⢿⣿⣿⣾⣾⣿⣿⢿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⣿⣿⣿⣿⣿⣏⣿⣿⣿⠿⢿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣩⣿⣿⣿⣟⣻⣿⣿⣿⣯⣿⣿⣿⣻⣽
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⣯⣛⣷⣿⣷⣶⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣿⣟⡻⣻⣿⣟⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣻⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣛⣲⣻⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⠛⠉⠚⣿⣛⣉⣿⣿⣿⣿⣿⡿⢿⣿⣿⢿⣿⣿⣿⣿⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⣿⣿⣏⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣿⣿⣿⣿⣿⡿⣿⣿⣿⣯⣿⣿⣾⣽⣿⣿⣿⣿⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⠏⣿⠏⣸⢑⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢯⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣻
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣶⣿⣼⣿⣿⣿⣟⣟⣹⣿⣿⣟⣿⣿⣿⣿⣟⣩⣗⣿⣿⡿⢿⣿⢿⣷⣻⣾⣿⣿⣷⣷⣿⣿⣿⣿⣿⢿⣷⣚
*/
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <cstring>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <cstdint>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll              long long int
#define ld              long double
#define mod             1000000007
#define inf             1e18
#define pb              push_back
#define vi              vector<ll>
#define vs              vector<string>
#define pii             pair<ll , ll>
#define ump             unordered_map
#define mp              make_pair
#define pq_max          priority_queue<ll>
#define pq_min          priority_queue<ll,vi,greater<ll> >
#define all(n)          n.begin(),n.end()
#define ff              first
#define ss              second
#define mid(l,r)        (l+(r-l)/2)
#define bitc(n)         __builtin_popcount(n)
#define loop(i,a,b)     for(int i=(a);i<=(b);i++)
#define looprev(i,a,b)  for(int i=(a);i>=(b);i--)
#define iter(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define log(args...)    { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define logarr(arr,a,b) for(int z=(a);z<=(b);z++) cout<<(arr[z])   ;cout<<endl;
 
 
 
 
void file_i_o(){
      ios_base::sync_with_stdio(0);
         cin.tie(0);
         cout.tie(0);
}
 
 
 void solve(){
         
          ll n;
        cin >> n;

        vi arr(n);
       loop(i,0,n-1){
          cin >> arr[i];
        }

           unordered_set<ll> oddSqrs;
            for (ll i = 1; i * i <= 10000; i += 2) {
                oddSqrs.insert(i * i);
            }

               ll total = 0;
        int happy = 0;

        loop(i, 0, n - 1) {
            total += arr[i];

            if (oddSqrs.find(total) != oddSqrs.end()) {
                happy++;
            }
        }

        cout << happy << "\n";
 
}
int main() {
      file_i_o();
// Write your code here....
                 int t;
                 cin>>t;
                 while(t--){
                    solve();
                 }
return 0;
}