Maximizing Mode Frequency

In a classroom game, there are \(n\) students (where \(n \le 10^6\)). Each student has two cards: a red card and a black card. The red card contains a non-negative integer \(a_i\) and the black card contains a non-negative integer \(b_i\) (with \(0 \le a_i, b_i \le 10^9\)). Each student can choose one of two moves: they can either play the red card (output \(a_i\)) or play the result of the bitwise XOR between their red and black card (i.e. output \(a_i \oplus b_i\)).

The teacher collects all the played numbers and the number that appears most frequently is called the mode. The students can collaborate and choose their moves optimally in order to maximize the frequency of the mode. Your task is to compute the maximum possible frequency of the mode that can be achieved.

Note: For each student, if the two choices are identical (i.e. \(a_i = a_i \oplus b_i\)), it is only counted once.

inputFormat

The first line contains an integer \(n\) indicating the number of students. Each of the next \(n\) lines contains two non-negative integers \(a_i\) and \(b_i\) separated by a space.

outputFormat

Output a single integer representing the maximum frequency of any number (mode) achievable under the optimal strategy.

sample

3
1 2
2 3
3 1

2