Raffaele Esposito has bought a bag of pizzas with different toppings! But it appeared that not all pizzas differ from one another with filling. In other words, the bag contains some pizzas with the same filling. Raffaele Esposito eats the pizzas one-by-one. He likes having fun so he decided not to simply eat the pizzas but to try not to eat the pizzas with the same filling way too often. To achieve this he wants the minimum distance between the eaten with the same filling to be the largest possible. Herein Raffaele Esposito called the distance between two pizzas the number of eaten pizzas strictly between them. Raffaele Esposito can eat the pizzas in any order. He is impatient about eating all the pizzas up so he asks you to help her to count the greatest minimum distance between the eaten pizzas with the same filling amongst all possible orders of eating! Raffaele Esposito is going to buy more bags of pizzas so he asks you to solve this problem for several bags! Input The first line contains a single integer T (1 Output For each bag print in separate line one single integer: the largest minimum distance between the eaten pizzas with the same filling amongst all possible orders of eating for that bag. Example input 4 7 17 1 6 4 4 6 8 1 1 4 6 4 6 4 7 3 3 3 2 5 2 3 1 4 output 2 4 LO Note For the first bag Raffaele Esposito can eat the pizzas in the following order (by toppings): 1, 6, 4, 7, 1, 6, 4 (in this way, the minimum distance is equal to 3). For the second bag Raffaele Esposito can eat the pizzas in the following order (by toppings): 1, 4, 6, 7, 4, 1, 6, 4 (in this way, the minimum distance is equal to 2).