Alice and Bob are playing a game. Initially, there is a set of string . Alice and Bob take turns to play, with Alice going first. Each turn, a player can choose a string from , remove it from , and select a character which appears in . Then, they remove all occurences of character from and divide into several substrings along these removed positions. They add all non-empty substrings to the set . The player who cannot make any move loses.

You are now given a tree with nodes. Each node contains a character. Let represent the string formed by concatenating the characters on the shortest path from node to node (including nodes and ). There are queries, and for each query, given nodes and , you need to determine the winner when . If Alice wins, also output the number of ways to make the first move.