// ⠉⠆⡁⠎⠡⠈⠆⠡⠈⡀⠀⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠀⠁⠈⠀⠁⠈⠀⠁⠈⠀⠁⠀⠀
// ⠌⠠⠀⠄⠁⡀⠂⠐⠀⠠⠀⠠⠐⠀⠠⠐⠀⠄⠐⠀⠐⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠐⠀⠂⠐⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠐⠀⠂⠐⠀⠠⠐⠀⠠⠐⠀⠠⠈⠀
// ⠈⡐⠀⠈⠀⠀⠁⠈⠀⠀⠀⢀⠀⠀⠀⠀⢀⠀⠠⠀⠂⠀⠀⠀⢀⠀⠀⢀⠀⠀⢀⠀⠀⠀⠂⠀⠀⠄⠀⠀⠀⢀⠀⠀⢀⠀⠀⠀⠄⠀⠀⠂⠀⠀⡀⠀⠀⠀⢀⠀⠀⢀⠀⠄⠀
// ⠐⠠⠀⠅⡈⠄⠨⡐⠀⠂⠐⠀⠀⠂⠁⠀⠀⡀⢀⠀⠀⠂⠐⠀⠀⠀⠂⠀⠀⠂⠀⠀⠂⠐⠀⠂⠀⠀⠂⠐⠀⠀⠀⠂⠀⠀⠂⠀⠀⠂⠐⠀⠂⠀⠀⠐⠈⠀⠀⠀⠂⠀⠐⠀⠀
// ⠈⡀⠁⠠⠀⠀⠁⢀⠠⠐⠀⠀⠂⠀⠄⠈⠀⠀⢀⠀⠐⠀⠀⠐⠀⠠⠀⠐⠀⠠⠀⠁⢀⠀⠄⠀⠂⠁⠀⠀⠐⠀⠂⠀⠐⠀⠠⠀⠁⠠⠀⠄⠀⠂⠁⠀⠀⡀⠁⠀⠠⠐⠀⠂⠀
// ⠀⡀⠠⠀⠄⠀⠂⠀⠀⢀⠀⠠⠀⠄⠀⠠⠀⠂⢀⠀⠄⠐⠈⠀⠠⠀⡀⠄⠠⠀⠀⠄⠀⡀⠀⠐⠀⡀⠐⠈⠀⠄⠠⠐⠀⠠⠀⠀⠄⢀⠀⠄⠐⠀⡀⠐⠀⡀⠄⠈⠀⢀⠀⠀⠀
// ⠐⠀⠀⠄⠂⠀⠀⠂⠀⠂⠀⠄⢀⠠⠀⠄⠠⠀⢀⠀⠄⠠⠀⠄⠠⠀⢀⠀⠄⠠⠀⠄⢀⠀⠄⠈⠀⢀⠠⠀⠄⠠⠀⢀⠠⠀⠄⠂⠀⠠⠀⠀⠄⠀⡀⠠⠀⢀⠀⠄⠈⠀⡀⠀⠀
// ⠀⠌⠀⠠⠀⢈⠀⢀⠀⠌⠀⠄⠀⠀⠀⠀⠀⠄⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠀⠠⠀⠀⠠⠀⠀⠐⠀⠀⠀⠄⠀⠀⠄⠀⠀⠄⠀⠀⠂⠀⠐⠀⠠⠀⠀⠀⠄⠀⠀⠀⠂⠀⠀⠀⠀
// ⢀⠂⠀⠁⠠⠀⠀⡀⠠⠀⠈⠀⠀⠀⠁⠈⠀⠀⠈⠀⠁⠈⠀⠀⠁⠀⠁⠀⠂⠁⠀⠁⢀⠀⠁⡀⠈⠀⡀⠂⠐⠈⠀⠐⠀⠀⡈⠀⡀⠁⠀⠂⢀⠀⠁⠀⠂⠐⠈⠀⠐⠈⠀⠀⠀
// ⠀⡄⠂⠈⠀⢠⠁⠀⠀⠐⠀⠁⠀⡄⠂⠀⠀⡄⢠⠀⠀⢠⠀⠁⠀⢠⠀⢠⠀⡄⠀⠁⠀⠀⡄⠀⠀⠁⠀⠀⡄⢠⠀⡄⠀⠁⠀⠀⠀⠀⠁⠀⠀⠀⠈⠀⢠⠀⢠⠀⡄⠀⠁⠀⠀
// ⠐⠀⠀⠂⠐⠀⠀⠠⠐⠀⠀⠄⠀⠀⠀⠠⠀⠀⠀⠀⠄⠀⠀⡀⠄⠀⠀⠀⡀⢀⠠⠀⠈⠀⡀⠀⠁⡀⠠⠁⠀⠀⡀⢀⠠⠀⠈⠀⠄⠈⠀⡈⠀⠁⡀⠈⠀⢀⠀⡀⢀⠠⠀⠀⠀
// ⠐⠈⠀⡀⠐⠈⠀⠀⠀⠐⠀⠀⠄⠂⠀⠀⢠⡀⠀⠀⡀⠠⠀⠀⠀⠀⠄⠂⠀⠀⠀⠄⠂⠀⠄⠐⠀⠀⠀⠄⠂⠀⠀⠀⠀⠄⠂⠀⠄⠂⠀⠀⠐⠀⠀⠐⠀⠀⠀⠀⠀⠀⠄⠐⠀
// ⠀⠀⠄⠀⢈⠀⠀⠀⠂⠈⠀⢀⠀⠀⡀⢨⣿⣷⡀⠀⠀⡀⠀⠂⠀⠈⠀⢀⠀⠁⢀⠀⠐⠀⡀⠐⠈⠀⠐⠀⠀⠈⠀⠁⢀⠀⠐⠀⠀⠐⠈⠀⠐⠈⠀⠐⠈⠀⠁⠀⠁⡀⠀⠀⠀
// ⠀⠠⠀⠂⠀⠠⠀⠀⠀⠀⠌⠀⠀⠀⣽⣿⣿⣿⡇⠀⠀⠀⠀⡀⠄⠀⠁⠀⢀⠈⠀⡀⠈⠀⡀⠠⠀⠁⢀⠂⠁⠈⠀⠈⠀⡀⠄⠈⠀⡐⠀⠁⠠⠀⠁⢀⠀⠁⠈⠀⠁⢀⠀⠐⠀
// ⠀⠀⠐⠀⠀⠁⠀⠀⠁⠀⠀⠀⠶⣼⣿⣿⣿⣿⡇⠀⠀⠠⠀⠀⠀⠀⠄⠠⠀⠠⠀⠀⠄⠀⠄⠀⠀⠂⠀⡀⠄⠀⠁⠠⠀⠀⠠⠀⠁⠀⠠⠀⠄⠀⠌⠀⠀⠈⠀⠄⠈⠀⠀⠀⠀
// ⠀⠀⢈⠀⠈⠀⠀⠀⠈⠀⢀⠀⣾⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⡀⠐⠀⠠⠀⠀⠠⠐⠀⠀⠂⠀⠐⠀⠂⠀⠀⠠⠐⠀⠠⠐⠀⠠⠐⠀⠂⠀⠄⠀⠂⠀⠐⠀⠁⠀⠄⠂⠐⠀⠠⠀
// ⠀⠀⠠⠀⠠⠀⠀⠐⠀⠐⠈⣿⣿⣿⣿⣿⣿⣿⠀⠀⡀⠁⠀⠀⠀⠀⡀⠀⠀⠁⢀⠀⠁⠀⠁⢀⠂⠀⠁⢀⠀⠀⠂⠀⠀⠂⢀⠀⡀⠐⠀⡀⠐⠀⠁⠀⠂⠁⢀⠀⡀⠀⠂⠀⠀
// ⠀⠀⠀⠄⠀⠀⠀⠀⠂⢀⣸⣿⣿⣿⣿⣿⣿⣿⠀⠀⢀⠠⠀⠀⠄⠀⠀⠀⠠⠈⠀⠀⢈⠀⠈⠀⠀⠄⠈⠀⢀⠠⠁⠈⠀⡀⠀⠀⡀⠠⠀⢀⠠⠀⠈⢀⠀⠄⠀⡀⠀⠠⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠈⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⡇⢀⠀⢀⠀⠀⠀⠠⠐⠀⠀⠀⠄⠐⠀⠀⠀⠂⠐⠀⠠⠐⠀⠀⠀⠀⠄⠐⠀⠠⠐⠀⠀⠀⠄⠀⠀⠂⠀⠀⠠⠀⠀⠠⠀⠄⠐⠀
// ⠀⠀⠠⠀⠈⠀⠀⠁⡄⣿⣿⣿⣿⣿⡿⠿⣿⡇⠀⠀⡀⠀⠈⠀⠀⢀⠀⠁⠀⡐⠀⠂⠁⠀⠂⢀⠈⠀⡀⠀⠁⠈⢀⠀⠀⠂⠀⢀⠀⠁⢀⠂⠈⠀⠐⠈⠀⡀⠐⠈⠀⢀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠠⠀⢰⣼⣿⣿⡿⢛⠡⡐⢂⣿⠁⠀⠀⠀⠠⠀⠀⠁⡀⠀⠄⠀⡀⠠⠀⢈⠀⠄⠀⠠⠀⢀⠀⠁⠠⠀⢀⠈⠀⢈⠀⠀⢈⠀⠀⡀⠁⡀⠄⠁⠀⠠⠀⠈⠀⡀⠠⠀
// ⠀⠀⠀⠀⠐⠀⣀⢰⣿⡿⠋⡔⢁⠢⢁⢾⡟⠀⠀⠀⠄⠀⡀⠄⠀⠀⠄⠠⠀⢀⠠⠀⠀⠀⠄⠐⠀⠠⠀⠀⠂⠀⠄⠀⠠⠀⢀⠠⠀⠂⠀⠄⠀⠄⠀⠀⠄⠂⠀⠄⠂⠀⠀⠀⠀
// ⠀⠀⠀⠀⠠⠀⠀⣾⠏⠶⠁⡔⡈⢢⠁⣾⡏⠀⠀⠂⠀⠀⠀⠀⠐⠀⠀⢀⠀⠀⠀⠀⠈⠀⠠⠐⠀⠠⠐⠀⠐⠀⠀⠂⠀⠄⠂⠀⠀⠐⠀⠀⠠⠀⠂⠀⠀⠐⠀⠀⠐⠀⠁⠀⠀
// ⠀⠀⠀⠀⠐⠂⢦⣿⢈⣛⠰⣀⠱⢀⢛⣽⠇⠀⠐⠀⠀⠁⠀⠁⠀⠀⠁⠀⠀⠁⠈⠀⠁⠀⡁⠀⠀⠄⠀⠂⠀⢈⠀⠐⠀⠀⠠⠀⠁⡀⠈⠀⠠⠀⠐⠈⠀⡀⠈⠀⡀⠈⠀⡀⠀
// ⠀⠀⠀⠄⠈⡁⣼⡯⠠⣿⠠⠐⣂⠡⢺⣿⢈⠀⠀⠀⠀⠠⠀⠐⠀⠀⠄⠠⠀⠈⠀⠀⠈⠀⡀⠐⠀⠠⠐⠀⠁⠀⠀⠄⠀⠁⠀⠠⠀⠀⠀⠁⠀⠠⠐⠀⠀⠀⠄⠂⠀⠠⠀⠀⠀
// ⠀⠀⠀⠀⠀⢔⣿⡧⠑⠦⢂⠱⠠⡘⣼⡇⠀⠀⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠂⠀⠀⢀⠀⠐⠀⠀⡀⠈⠀⠀⠀⠀⠂⠀⠀⠀⠐⠀⠁⢀⠀⠀⠀⠁⠀⠀⠀⢀⠀⠀⠐⠀
// ⠀⠀⠀⠁⠀⣺⣿⡗⡁⢛⠠⡁⠆⣱⣿⠀⠀⠂⠀⠐⠀⡀⠄⠂⠁⠀⠀⠁⠀⠀⠀⡀⠈⠀⡀⠀⠀⠂⠀⠀⠀⠐⠈⠀⡀⠄⠀⠁⠀⢀⠀⠀⠀⠀⠀⠁⠀⠀⠁⠀⠀⠀⠀⢀⠀
// ⠀⠀⠀⠀⠀⣼⡿⣏⠐⡡⠂⠥⣈⢳⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠐⠀⠁⢀⠀⠀⠀⡀⠠⠀⠀⠈⠀⠀⠄⠀⡀⠀⠀⡀⠈⠀⠀⠀⠐⠈⠀⠐⠀⠀⠂⠀⠂⠀⠄⠂⠀⠀
// ⠀⠀⠀⠀⠀⢸⣿⡇⡘⢠⠑⢂⠤⣿⣇⣤⣤⣤⣦⣥⣤⣤⣤⣤⣤⣄⣀⣀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠄⠠⠐⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⢀⠀⡀⠀⢀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⢸⣿⡇⠱⡈⠔⡨⣴⣿⠛⠩⡉⢍⠩⡉⢍⡙⡙⢋⡙⢛⠻⠿⣦⣤⣄⡀⠀⠀⠀⠠⠐⠀⠀⠀⠀⠀⠀⣀⣀⣀⣠⣄⣦⣴⣤⣤⣴⣴⣾⣶⢾⡶⢷⣶⣾⣶⣤⣤⣦
// ⠀⠀⡀⠁⠀⠈⣿⣯⠐⡄⢃⠴⠟⠣⠌⡡⢐⠊⡰⠁⢆⠰⢈⠔⡰⠈⡔⢂⠤⢉⡉⢛⠷⣦⣤⡀⠀⢀⣤⣤⣴⡶⠿⠟⡛⠋⡍⡉⠥⡈⠔⡰⢀⠆⠤⠐⣂⠐⢢⣰⣿⣿⣿⣿⣿
// ⠀⠀⠀⠀⠀⢢⣿⣿⡶⠈⡔⢠⠊⡁⢆⠡⢌⢂⠱⡈⠆⡱⠈⡔⠠⢃⠜⠠⠒⠤⡘⠄⡊⠤⠙⢻⣾⣟⠋⢌⡐⠄⢃⠢⡁⠎⡐⠄⣃⠘⡰⠐⡨⠐⡌⢡⠐⣼⣾⣿⣿⣿⣿⣿⣿
// ⠀⠀⠀⠀⢠⣿⣋⢙⠣⣁⠒⡠⠑⡨⠄⢊⠄⡊⠔⡠⢃⠔⢡⢂⠱⡈⢆⠡⡉⠔⡠⠃⠜⡠⢉⠤⡈⠿⣾⡠⠐⡌⢂⠅⠢⢑⡈⢒⡀⠣⡐⢡⠂⠱⠐⣦⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⠀⠀⠀⢀⣿⠇⠴⡈⠰⡀⠆⡁⠎⡐⠌⢢⠘⠄⢣⠐⡡⢊⠔⡈⢆⡑⠢⡑⡈⢆⠱⢈⠆⡑⠢⡐⠤⠡⠹⣿⣥⢶⣬⢖⡳⣖⡞⣖⢾⣱⣾⣶⣿⣾⣿⣿⣿⡿⠿⠿⠛⠛⠋⠉⠛
// ⠀⠀⢀⣸⡟⡸⢇⠰⢁⠢⢑⠨⡐⢡⠘⢄⠃⠎⡄⠣⡐⠡⢌⡐⢢⠈⡅⢢⠑⡂⠜⡠⢊⡐⠡⠒⡈⢅⠊⣽⣿⠛⠿⠿⠛⠛⠛⠛⠛⠛⠋⠛⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⢠⣿⢃⡍⢫⠐⣡⣾⣶⡷⢶⣧⣌⠢⠘⡥⠘⠤⣁⠃⢆⡘⢄⠃⡌⢂⠆⠱⡈⠤⢡⠐⡡⠃⢌⠰⢈⠴⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠀⠄⠈⠀
// ⠀⠀⣾⡏⠦⡐⢡⢺⣿⣿⣯⡀⢀⣿⣿⢠⠃⢄⢃⠒⡄⢩⠐⢌⠂⡱⠈⠆⡌⠱⣀⠣⠄⢃⠔⡉⢄⠊⡄⢚⣿⡇⠀⠠⠀⠀⠂⠀⠄⠠⠀⠀⠐⠀⠀⠂⠀⠐⠀⠀⠄⠂⠀⠠⠀
// ⠀⣾⡟⠰⢠⠑⠢⢸⣿⣿⣿⣿⣿⣿⡿⠰⣈⠢⠌⠰⡈⢆⡘⠄⢣⠐⣉⠒⡈⠅⡄⢢⢉⡄⢊⡔⠈⡔⠨⢰⣿⡇⠀⠀⠁⠀⠂⠁⠀⠀⠀⠁⠀⠀⠁⠀⠀⠂⠐⠀⠀⡀⠄⠂⠀
// ⣼⣿⣷⣷⣦⣇⡑⠢⢘⢻⠿⣿⡿⠛⢄⠃⡄⢒⠨⡁⠔⢂⠤⣉⠂⠥⣈⢂⠱⢈⣴⣾⠾⠿⢿⣶⡁⢢⠑⢺⣿⠁⠀⠈⠀⠀⡀⠐⠀⡁⠀⠁⡈⠀⠄⠈⠀⠀⠀⠈⠀⠀⠀⠀⠀
// ⣿⣿⡿⣟⣿⣿⣷⣅⠊⡄⢒⠠⢡⠉⡄⢊⠰⢈⠡⡘⢈⠆⡰⣿⣷⠆⡰⠀⢎⢰⣿⣿⣦⣥⣾⣿⣷⠀⢎⣹⡇⢉⠀⠀⠠⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠄⠀⠐⠀⠄⠀⠀
// ⣿⡿⣽⣿⣳⡿⣿⣿⡐⠌⡄⢃⢂⡑⢿⣦⣁⣊⠤⢑⣈⣔⣠⣙⠣⠐⠤⢉⠄⠚⢟⣿⣿⣿⣿⣿⢏⠌⢢⣿⠁⠀⠀⠀⠀⠀⠠⠀⠀⠀⠐⠀⠐⠀⠀⠐⠀⠀⠀⠂⠀⠀⠄⠀⠀
// ⣿⣿⢯⣿⣽⣿⣿⣿⠁⢎⡐⠌⡄⠒⡠⢹⣿⣿⣿⣿⣿⣿⣿⣿⣷⣍⡰⠈⡌⡘⢠⢊⡙⠻⡙⠋⡄⢊⣼⡟⠀⠀⠀⠀⠀⠁⠀⠀⡀⠈⠀⡀⠀⠀⠁⠀⢀⠀⢀⠀⠁⢀⠀⠀⠀
// ⢻⣿⣿⣳⣿⣿⣿⠏⢨⠐⡄⢊⠄⢣⠐⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣷⣶⠂⠰⡁⠔⠡⢂⣥⣾⡇⠀⠈⠀⠀⠈⠀⠈⠀⠀⠀⠀⠀⠠⠀⠀⠠⠀⠀⠀⠀⡀⠀⠀⠀⠀
// ⠠⢻⣿⠟⠟⡛⠡⣈⢂⠱⢈⠂⡜⠠⡑⢼⣿⣟⣿⣻⣟⡿⣿⣿⣿⣿⣿⣿⠍⡐⠤⡈⠥⠐⣉⣴⣿⣿⣿⣿⠀⣀⣀⣀⣤⣤⣤⣀⣠⣿⣤⠀⠀⠀⠠⠀⠀⠀⠂⠀⠀⠐⠀⠀⠀
// ⢀⠃⢿⣷⠈⡄⠓⡀⠆⠱⣈⠒⢠⠑⡈⣾⣿⣞⣷⣻⢾⣽⣳⢯⣿⣿⡟⡘⠤⢁⠒⠤⢁⢃⣼⣿⣟⣷⣿⡿⠿⠛⢋⠍⡩⢉⠍⡩⢙⢻⣿⣷⡷⡄⠀⠀⠐⠀⢀⠈⠀⠀⡀⠈⠀
// ⠠⡉⢄⠻⣷⡌⢂⠥⢉⠒⠤⡉⢄⠊⠔⢻⣿⣞⡷⣯⣟⡾⣽⣯⣿⠏⠰⡐⠌⢢⠁⠎⡠⢿⣿⡿⣽⣿⡿⠁⢆⠩⡐⢌⠰⣈⠰⢀⠃⡜⠻⣿⣷⠃⠀⠀⠠⠀⠀⢀⠈⠀⠀⠀⠀
// ⠠⠑⡂⢌⢹⣿⣖⠰⠈⡌⢂⠅⢢⢉⠰⢉⣿⣯⣟⡷⣯⣟⣷⡟⠡⠌⡁⢆⠩⡄⢃⠜⠠⡙⢿⣿⡿⠋⠤⢉⠄⢢⠁⢎⠐⡄⢢⠁⠎⢠⣽⣿⡇⠀⠀⠀⠄⠀⠂⠀⠠⠀⠀⠀⠀
// ⠐⡡⢘⠠⢂⠌⡙⢠⠃⡰⢁⡘⠄⢢⠁⢆⠘⢿⣯⣿⣷⠟⡉⢄⠣⢘⠰⠈⢆⠘⡠⢊⣥⣶⠿⠋⠤⢉⠔⡨⢘⠠⡉⢄⠊⡄⠃⡌⣸⣼⠿⠟⠋⠀⠀⠀⠄⠂⠀⠂⠀⠐⠀⠈⠀
// ⠠⢃⠜⡠⢃⠄⡃⢄⠸⢀⢻⣄⡸⢀⠃⠜⡘⣀⠛⡘⠠⡘⠠⢄⠸⢀⠜⢃⠄⣣⣤⡿⠟⡀⢄⠛⡠⢘⠠⡀⠇⢠⠃⡜⠠⠘⣃⣤⣿⠇⠀⠀⠀⠀⠠⠀⠀⠀⠀⠄⠃⠀⠀⠀⠀
// ⠦⠡⢎⠰⢁⠎⡰⠈⡔⠨⣀⠛⣿⣿⢾⣶⣴⣤⣮⣴⣥⣢⣑⣢⣌⠢⡘⣼⠟⡋⠍⡐⢂⠅⡊⠔⡁⠆⡑⢠⠉⡔⠂⡔⢡⣳⡾⠋⠀⠀⡀⠠⠀⠀⠐⠀⠈⠀⠀⠂⠀⠀⠁⠀⠀
// ⠒⢡⠂⢎⠐⡊⠔⣁⠢⡑⠄⡊⢌⠻⣿⣼⣭⣛⣼⣭⣟⠿⢛⠋⡩⠄⢡⠂⠜⡠⠑⡌⢨⠐⡡⢘⠠⡑⠨⠄⢃⡰⣡⣾⠟⠋⠀⠀⠠⠀⠀⡀⠀⠁⡀⠠⠀⠀⠄⠠⠀⠠⠁⠀⠀
// ⣙⡄⢋⡄⢣⢉⠒⡄⠢⢑⠨⡐⢢⢁⢂⡉⠍⢋⠍⡡⠂⡜⢀⠣⡐⡘⢄⠊⡔⠡⣁⠢⡁⢆⣡⢢⡱⣴⣷⣿⡿⠟⠋⠀⠀⠀⠀⠀⠄⠀⠀⠀⠠⠀⠀⠀⠀⠄⠀⠀⠠⠀⠀⠀⠀
// ⢥⠊⠥⡈⢆⠡⡃⣌⠱⣈⢂⡑⢢⢈⠄⢢⠉⡄⢊⠤⠑⣈⠢⢡⠐⡡⠌⢒⡈⢒⡀⣾⣿⠻⣜⣧⣿⠿⠛⠉⠀⠀⠀⠀⠐⠀⠈⠀⠀⢀⠀⠁⢀⠀⠂⠈⠀⠀⠐⠈⠀⢀⠈⠀⠀
// ⠦⡙⢢⠑⡌⢢⠑⠤⠒⡄⢢⠐⠢⢌⡘⠤⠡⡘⢄⠢⡑⠄⢆⠡⢊⠔⡈⢆⠘⠤⣰⣿⠿⠛⠛⠁⠀⠀⠀⠀⢀⠀⠂⠈⠀⠀⠠⠈⠀⢀⠀⡀⠀⠀⠀⡀⠠⠀⠄⠀⡈⠀⠀⠀⠀
// ⢣⡑⢢⠑⡘⠤⣉⠒⡡⢘⡀⠎⠱⣀⠒⡄⢣⠐⡌⠒⢌⡘⠠⢃⠌⣂⠱⢈⠆⢲⣿⠃⠀⠀⠀⠀⠀⠠⠀⠀⠀⠀⡀⠀⠂⠀⠄⠀⠄⠀⠀⠀⠀⠐⠀⠀⠄⠀⠠⠀⠀⠐⠀⠀⠀
// ⡥⢊⠤⡉⢆⠱⣀⢣⠐⡡⢄⡉⢒⠠⢡⠘⡠⠡⢌⡑⢂⠌⡑⣈⠒⡠⢃⠢⠌⣻⡿⠀⠦⠁⠀⠐⠀⠀⠠⠀⠁⠀⠀⠄⠐⠀⠀⠀⡀⠠⠀⠂⠁⠀⠂⠀⠀⠂⠀⠀⠁⠀⠂⠈⠀
// ⠲⡡⢢⠑⡌⠒⠤⢢⠑⡐⢂⠌⢢⠑⠢⡁⢆⡑⠢⢌⠢⢘⠰⣀⠣⡐⠡⠌⢂⣿⣷⠀⠀⠀⠀⠀⠂⠁⠀⠐⠀⠁⠀⠀⠀⠀⠠⠀⠀⢀⠀⡀⠈⠀⠐⠈⠀⠐⠈⠀⠁⢀⠂⠀⠀
// ⠛⡱⢃⠫⠜⠫⡜⢣⠚⡘⠄⡊⠔⡨⠑⡐⠢⡐⢡⠂⡜⠠⢡⠐⣂⠡⢃⡘⠤⠘⣟⣷⣎⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//_______________________________________________________________________________________
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
struct DSU{
    vector<int>fa;
    DSU(int n)
    {
        for(int i = 0; i <= n; i++)
            fa.push_back(i);
    }
    int found(int x)
    {
        return fa[x] == x ? x : (fa[x] = found(fa[x]));
    }
    void merge(int x, int y)
    {
        x = found(x), y = found(y);
        if(x < y){swap(x, y);};
        if(x != y)
        {
            fa[x] = y;
        }
    }
};
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int> >g1(n+10);
    vector<vector<int> >g2(n+10);
    DSU dsu1(n+1);
    DSU dsu2(n+1);
    for(int i = 0; i < m; i++)
    {
        int a, b, col;
        cin >> a >> b >> col;
        if(col == 0)
        {
            g1[a].push_back(b);
            g1[b].push_back(a);
            dsu1.merge(a,b);
        }
        else
        {
            g2[a].push_back(b);
            g2[b].push_back(a);
            dsu2.merge(a,b);
        }
    }
    vector<int>vis(n+10);
    vector<int>pend;
    int ans = 0;
    map<vector<int>, int>mp;
    auto dfs = [&](auto &&dfs, int now, int cnt)
    {
        if(cnt > 4)
        {
            
            return;
        }
        pend.push_back(now);
        bool op = true;
        int num = 0;
        if(cnt != 1)
        {
            vector<int> x(cnt+10);
            for(int i = 0; i < cnt; i ++)
            {
                for(int k = i; k < cnt; k++)
                {
                    for(auto j : g2[pend[i]])
                    {
                        if(j == pend[k])
                        {
                            x[i] = 1;
                            x[k] = 1;
                            break;
                        }
                    }
                }
            }
            for(int i = 0; i < cnt; i++)
            {
                if(!x[i])
                    op = false;
            }
        }
        
        if(op)
        {
            sort(pend.begin(), pend.end());
            if(!mp[pend])
            {
                
                mp[pend] = 1;
                ans++;
            }
            
        }

        
        for(auto i : g1[now])
        {
            if(!vis[i])
            {
                vis[i] = 1;
                dfs(dfs, i, cnt+1);
                vis[i] = 0;
            }
        }
        pend.pop_back();
    };
    auto dfs2 = [&](auto &&dfs2, int now, int cnt)
    {
        if(cnt > 4)
        {
            return;
        }
        pend.push_back(now);
        
        bool op = true;
        int num = 0;
        if(cnt != 1)
        {
            vector<int> x(cnt+10);
            for(int i = 0; i < cnt; i ++)
            {
                for(int k = i; k < cnt; k++)
                {
                    for(auto j : g1[pend[i]])
                    {
                        if(j == pend[k])
                        {
                            x[i] = 1;
                            x[k] = 1;
                            break;
                        }
                    }
                }
            }
            for(int i = 0; i < cnt; i++)
            {
                if(!x[i])
                    op = false;
            }
        }
        
        if(op)
        {
            sort(pend.begin(), pend.end());
            if(!mp[pend])
            {
                
                mp[pend] = 1;
                ans++;
            }
            
        }

        
        for(auto i : g2[now])
        {
            if(!vis[i])
            {
                vis[i] = 1;
                dfs2(dfs2, i, cnt+1);
                vis[i] = 0;
            }
        }
        pend.pop_back();
    };
    for(int i = 1; i <= n; i++)
    {
        vis[i] = 1;
        dfs(dfs, i, 1);
        dfs2(dfs2, i, 1);
    }
    cout << ans << '\n';
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    // int _;
    // cin >> _;
    // while(_--)
    {
        solve();
    }
    return 0;
}